Comment 12 for bug 442651

I looked into this now and it seems like there is a bug in the apt ordering code that makes this fail when it tries to figure out what to do with openoffice.org-common (a dependency of openoffice.org-core) when the calculation of the ordering happens. A easy workaround is to help the ordering algorithm a bit by doing:

--- control.in.orig 2009-10-16 08:59:14.868431842 +0200
+++ control.in 2009-10-16 08:59:16.570931100 +0200
@@ -654,7 +654,7 @@
 Package: openoffice.orgVER-evolution
 Architecture: %OOO_ARCHS%
 Section: gnome
-Pre-Depends: openoffice.orgVER-core (>= 1:3.1.0-2), debconf (>= 0.5) | debconf-2.0, procps
+Pre-Depends: openoffice.orgVER-common (>= (>= 1:3.1.0-2), openoffice.orgVER-core (>= 1:3.1.0-2), debconf (>= 0.5) | debconf-2.0, procps
 Depends: openoffice.orgVER-core (= ${binary:Version}),
  openoffice.orgVER-base,
  ${shlibs:Depends},
@@ -724,7 +724,7 @@
 Package: openoffice.orgVER-filter-binfilter
 Section: misc
 Architecture: %OOO_BINFILTER_ARCHS%
-Pre-Depends: openoffice.orgVER-core (>= 1:3.1.0-2), debconf (>= 0.5) | debconf-2.0, procps
+Pre-Depends: openoffice.orgVER-common (>= (>= 1:3.1.0-2), openoffice.orgVER-core (>= 1:3.1.0-2), debconf (>= 0.5) | debconf-2.0, procps
 Depends: openoffice.orgVER-core (= ${binary:Version}),
  ${shlibs:Depends},
  ${misc:Depends}

This seems to fix it.