Comment 4 for bug 274365

I don't think a PreDepends is necessary in that case. It may be an issue with a circular dependency.

Here is a log of the postinst:

Setting up sun-java6-jre (6-07-4ubuntu2) ...

Setting up libcommons-daemon-java (1.0.2~svn20061127-9ubuntu1) ...

Setting up jsvc (1.0.2~svn20061127-9ubuntu1) ...
Setting up libcommons-collections-java (2.1.1-8ubuntu1) ...

Setting up libcommons-pool-java (1.3-1ubuntu1) ...

Setting up libcommons-dbcp-java (1.2.2-1ubuntu1) ...
Setting up libservlet2.5-java (6.0.18-0ubuntu1) ...
Setting up libtomcat6-java (6.0.18-0ubuntu1) ...
Setting up tomcat6-common (6.0.18-0ubuntu1) ...
Setting up tomcat6 (6.0.18-0ubuntu1) ...
Adding system user `tomcat6' (UID 108) ...
Adding new group `tomcat6' (GID 119) ...
Adding new user `tomcat6' (UID 108) with group `tomcat6' ...
Not creating home directory `/usr/share/tomcat6'.
 * Starting Tomcat servlet engine tomcat6
   ...fail!
invoke-rc.d: initscript tomcat6, action "start" failed.
dpkg: error processing tomcat6 (--configure):
 subprocess post-installation script returned error exit status 1
Setting up sun-java6-bin (6-07-4ubuntu2) ...

sun-java6-jre is configured before tomcat6. sun-java6-jre depends on sun-java6-bin (which is the package that provides the java binary) however sun-java6-bin is configure after sun-java6-jre (and after tomcat6 which fails).

There may be an issue in the dependencies between sun-java6-jre and sun-java6-bin:

$ apt-cache depends sun-java6-jre sun-java6-bin | grep sun-java6
sun-java6-bin
  Depends: sun-java6-jre
sun-java6-jre
 |Depends: sun-java6-bin