I have run into the problem 3 days ago while simple installation of bootchart. The state of the rest of the system was from 2006-06-10, I have just installed bootchart which triggered the upgrade of some packages.
I am attaching log of the upgrade which caused the problem.

I have tried dist-upgrade since today, but it doesn't help.

Here is the list of packages which I have upgraded and which caused the problem:

2007-08-05 23:49:34 upgrade zlib1g 1:1.2.3-14ubuntu1 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:34 status half-configured zlib1g 1:1.2.3-14ubuntu1
2007-08-05 23:49:34 status unpacked zlib1g 1:1.2.3-14ubuntu1
2007-08-05 23:49:34 status half-installed zlib1g 1:1.2.3-14ubuntu1
2007-08-05 23:49:34 status half-installed zlib1g 1:1.2.3-14ubuntu1
2007-08-05 23:49:34 status unpacked zlib1g 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:34 status unpacked zlib1g 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:34 status unpacked zlib1g 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:34 status half-configured zlib1g 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:41 status installed zlib1g 1:1.2.3.3.dfsg-5ubuntu2
2007-08-05 23:49:42 install liblzo2-2 <none> 2.02-3
2007-08-05 23:49:42 status half-installed liblzo2-2 2.02-3
2007-08-05 23:49:42 status unpacked liblzo2-2 2.02-3
2007-08-05 23:49:42 status unpacked liblzo2-2 2.02-3
2007-08-05 23:49:42 upgrade libgnutls13 1.6.2-1 1.6.3-1
2007-08-05 23:49:42 status half-configured libgnutls13 1.6.2-1
2007-08-05 23:49:42 status unpacked libgnutls13 1.6.2-1
2007-08-05 23:49:42 status half-installed libgnutls13 1.6.2-1
2007-08-05 23:49:42 status half-installed libgnutls13 1.6.2-1
2007-08-05 23:49:43 status unpacked libgnutls13 1.6.3-1
2007-08-05 23:49:43 status unpacked libgnutls13 1.6.3-1
2007-08-05 23:49:43 upgrade libglib2.0-0 2.13.2-0ubuntu1 2.13.7-1ubuntu4
2007-08-05 23:49:43 status half-configured libglib2.0-0 2.13.2-0ubuntu1
2007-08-05 23:49:43 status unpacked libglib2.0-0 2.13.2-0ubuntu1
2007-08-05 23:49:43 status half-installed libglib2.0-0 2.13.2-0ubuntu1
2007-08-05 23:49:43 status half-installed libglib2.0-0 2.13.2-0ubuntu1
2007-08-05 23:49:43 status unpacked libglib2.0-0 2.13.7-1ubuntu4
2007-08-05 23:49:43 status unpacked libglib2.0-0 2.13.7-1ubuntu4
2007-08-05 23:49:43 upgrade libxml2 2.6.28.dfsg-1ubuntu1 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:43 status half-configured libxml2 2.6.28.dfsg-1ubuntu1
2007-08-05 23:49:43 status unpacked libxml2 2.6.28.dfsg-1ubuntu1
2007-08-05 23:49:43 status half-installed libxml2 2.6.28.dfsg-1ubuntu1
2007-08-05 23:49:43 status half-installed libxml2 2.6.28.dfsg-1ubuntu1
2007-08-05 23:49:43 status unpacked libxml2 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:43 status unpacked libxml2 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:43 install libcroco3 <none> 0.6.1-1build2
2007-08-05 23:49:43 status half-installed libcroco3 0.6.1-1build2
2007-08-05 23:49:43 status unpacked libcroco3 0.6.1-1build2
2007-08-05 23:49:43 status unpacked libcroco3 0.6.1-1build2
2007-08-05 23:49:44 upgrade libfreetype6 2.2.1-6ubuntu1 2.3.5-1
2007-08-05 23:49:44 status half-configured libfreetype6 2.2.1-6ubuntu1
2007-08-05 23:49:44 status unpacked libfreetype6 2.2.1-6ubuntu1
2007-08-05 23:49:44 status half-installed libfreetype6 2.2.1-6ubuntu1
2007-08-05 23:49:44 status half-installed libfreetype6 2.2.1-6ubuntu1
2007-08-05 23:49:44 status unpacked libfreetype6 2.3.5-1
2007-08-05 23:49:44 status unpacked libfreetype6 2.3.5-1
2007-08-05 23:49:44 upgrade libgtk2.0-0 2.10.12-2ubuntu3 2.11.6-1ubuntu3
2007-08-05 23:49:44 status half-configured libgtk2.0-0 2.10.12-2ubuntu3
2007-08-05 23:49:44 status unpacked libgtk2.0-0 2.10.12-2ubuntu3
2007-08-05 23:49:44 status half-installed libgtk2.0-0 2.10.12-2ubuntu3
2007-08-05 23:49:45 status half-installed libgtk2.0-0 2.10.12-2ubuntu3
2007-08-05 23:49:45 status unpacked libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:45 status unpacked libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:45 upgrade libgtk2.0-common 2.10.12-2ubuntu3 2.11.6-1ubuntu3
2007-08-05 23:49:45 status half-configured libgtk2.0-common 2.10.12-2ubuntu3
2007-08-05 23:49:45 status unpacked libgtk2.0-common 2.10.12-2ubuntu3
2007-08-05 23:49:45 status half-installed libgtk2.0-common 2.10.12-2ubuntu3
2007-08-05 23:49:45 status half-installed libgtk2.0-common 2.10.12-2ubuntu3
2007-08-05 23:49:45 status unpacked libgtk2.0-common 2.11.6-1ubuntu3
2007-08-05 23:49:45 status unpacked libgtk2.0-common 2.11.6-1ubuntu3
2007-08-05 23:49:45 upgrade libpango1.0-common 1.17.1-0ubuntu1 1.17.5-1ubuntu1
2007-08-05 23:49:45 status half-configured libpango1.0-common 1.17.1-0ubuntu1
2007-08-05 23:49:47 status unpacked libpango1.0-common 1.17.1-0ubuntu1
2007-08-05 23:49:47 status half-installed libpango1.0-common 1.17.1-0ubuntu1
2007-08-05 23:49:47 status half-installed libpango1.0-common 1.17.1-0ubuntu1
2007-08-05 23:49:47 status unpacked libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:47 status unpacked libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:47 upgrade libpango1.0-0 1.17.1-0ubuntu1 1.17.5-1ubuntu1
2007-08-05 23:49:47 status half-configured libpango1.0-0 1.17.1-0ubuntu1
2007-08-05 23:49:47 status unpacked libpango1.0-0 1.17.1-0ubuntu1
2007-08-05 23:49:47 status half-installed libpango1.0-0 1.17.1-0ubuntu1
2007-08-05 23:49:48 status half-installed libpango1.0-0 1.17.1-0ubuntu1
2007-08-05 23:49:48 status unpacked libpango1.0-0 1.17.5-1ubuntu1
2007-08-05 23:49:48 status unpacked libpango1.0-0 1.17.5-1ubuntu1
2007-08-05 23:49:48 install libgail18 <none> 1.19.6-0ubuntu1
2007-08-05 23:49:48 status half-installed libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:48 status unpacked libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:48 status unpacked libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:48 install libgail-common <none> 1.19.6-0ubuntu1
2007-08-05 23:49:48 status half-installed libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:48 status unpacked libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:48 status unpacked libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:48 upgrade libglade2-0 1:2.6.0-4 1:2.6.2-1
2007-08-05 23:49:48 status half-configured libglade2-0 1:2.6.0-4
2007-08-05 23:49:48 status unpacked libglade2-0 1:2.6.0-4
2007-08-05 23:49:48 status half-installed libglade2-0 1:2.6.0-4
2007-08-05 23:49:49 status half-installed libglade2-0 1:2.6.0-4
2007-08-05 23:49:49 status unpacked libglade2-0 1:2.6.2-1
2007-08-05 23:49:49 status unpacked libglade2-0 1:2.6.2-1
2007-08-05 23:49:49 install libgnomecanvas2-common <none> 2.19.1-0ubuntu2
2007-08-05 23:49:49 status half-installed libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:49 status unpacked libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:49 status unpacked libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:49 install libgnomecanvas2-0 <none> 2.19.1-0ubuntu2
2007-08-05 23:49:49 status half-installed libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:49 status unpacked libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:49 status unpacked libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:49 install libgnomecups1.0-1 <none> 0.2.2-5ubuntu1
2007-08-05 23:49:49 status half-installed libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:49 status unpacked libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:49 status unpacked libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:49 install libgnomeprint2.2-data <none> 2.18.0-2
2007-08-05 23:49:49 status half-installed libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:50 install libgnomeprint2.2-0 <none> 2.18.0-2
2007-08-05 23:49:50 status half-installed libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:50 install libgnomeprintui2.2-common <none> 2.18.0-2
2007-08-05 23:49:50 status half-installed libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:50 install libgnomeprintui2.2-0 <none> 2.18.0-2
2007-08-05 23:49:50 status half-installed libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:50 status unpacked libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:51 install libgsf-1-common <none> 1.14.5-0ubuntu1
2007-08-05 23:49:51 status half-installed libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:51 status unpacked libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:51 status unpacked libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:51 install libgsf-1-114 <none> 1.14.5-0ubuntu1
2007-08-05 23:49:51 status half-installed libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:51 status unpacked libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:51 status unpacked libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:51 install librsvg2-2 <none> 2.18.0-1
2007-08-05 23:49:51 status half-installed librsvg2-2 2.18.0-1
2007-08-05 23:49:51 status unpacked librsvg2-2 2.18.0-1
2007-08-05 23:49:51 status unpacked librsvg2-2 2.18.0-1
2007-08-05 23:49:51 install librsvg2-bin <none> 2.18.0-1
2007-08-05 23:49:51 status half-installed librsvg2-bin 2.18.0-1
2007-08-05 23:49:51 status unpacked librsvg2-bin 2.18.0-1
2007-08-05 23:49:51 status unpacked librsvg2-bin 2.18.0-1
2007-08-05 23:49:52 install bootchart <none> 0.9-0ubuntu7
2007-08-05 23:49:52 status half-installed bootchart 0.9-0ubuntu7
2007-08-05 23:49:52 status unpacked bootchart 0.9-0ubuntu7
2007-08-05 23:49:52 status unpacked bootchart 0.9-0ubuntu7
2007-08-05 23:49:52 status unpacked liblzo2-2 2.02-3
2007-08-05 23:49:52 status half-configured liblzo2-2 2.02-3
2007-08-05 23:49:53 status installed liblzo2-2 2.02-3
2007-08-05 23:49:53 status unpacked libgnutls13 1.6.3-1
2007-08-05 23:49:53 status half-configured libgnutls13 1.6.3-1
2007-08-05 23:49:53 status installed libgnutls13 1.6.3-1
2007-08-05 23:49:53 status unpacked libglib2.0-0 2.13.7-1ubuntu4
2007-08-05 23:49:53 status half-configured libglib2.0-0 2.13.7-1ubuntu4
2007-08-05 23:49:53 status installed libglib2.0-0 2.13.7-1ubuntu4
2007-08-05 23:49:53 status unpacked libxml2 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:53 status half-configured libxml2 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:53 status installed libxml2 2.6.29.dfsg-1ubuntu1
2007-08-05 23:49:53 status unpacked libcroco3 0.6.1-1build2
2007-08-05 23:49:53 status half-configured libcroco3 0.6.1-1build2
2007-08-05 23:49:53 status installed libcroco3 0.6.1-1build2
2007-08-05 23:49:53 status unpacked libfreetype6 2.3.5-1
2007-08-05 23:49:53 status half-configured libfreetype6 2.3.5-1
2007-08-05 23:49:53 status installed libfreetype6 2.3.5-1
2007-08-05 23:49:53 status unpacked libgtk2.0-common 2.11.6-1ubuntu3
2007-08-05 23:49:53 status half-configured libgtk2.0-common 2.11.6-1ubuntu3
2007-08-05 23:49:53 status installed libgtk2.0-common 2.11.6-1ubuntu3
2007-08-05 23:49:53 status unpacked libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:53 status unpacked libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:53 status half-configured libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:56 status installed libpango1.0-common 1.17.5-1ubuntu1
2007-08-05 23:49:56 status unpacked libpango1.0-0 1.17.5-1ubuntu1
2007-08-05 23:49:56 status half-configured libpango1.0-0 1.17.5-1ubuntu1
2007-08-05 23:49:56 status installed libpango1.0-0 1.17.5-1ubuntu1
2007-08-05 23:49:56 status unpacked libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:56 status unpacked libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:56 status half-configured libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:56 status installed libgtk2.0-0 2.11.6-1ubuntu3
2007-08-05 23:49:56 status unpacked libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:56 status half-configured libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:57 status installed libgail18 1.19.6-0ubuntu1
2007-08-05 23:49:57 status unpacked libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:57 status half-configured libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:57 status installed libgail-common 1.19.6-0ubuntu1
2007-08-05 23:49:57 status unpacked libglade2-0 1:2.6.2-1
2007-08-05 23:49:57 status half-configured libglade2-0 1:2.6.2-1
2007-08-05 23:49:57 status installed libglade2-0 1:2.6.2-1
2007-08-05 23:49:57 status unpacked libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:57 status half-configured libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:57 status installed libgnomecanvas2-common 2.19.1-0ubuntu2
2007-08-05 23:49:57 status unpacked libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:57 status half-configured libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:57 status installed libgnomecanvas2-0 2.19.1-0ubuntu2
2007-08-05 23:49:57 status unpacked libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:57 status half-configured libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:57 status installed libgnomecups1.0-1 0.2.2-5ubuntu1
2007-08-05 23:49:57 status unpacked libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:57 status half-configured libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:57 status installed libgnomeprint2.2-data 2.18.0-2
2007-08-05 23:49:57 status unpacked libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:57 status half-configured libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:57 status installed libgnomeprint2.2-0 2.18.0-2
2007-08-05 23:49:57 status unpacked libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:57 status half-configured libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:57 status installed libgnomeprintui2.2-common 2.18.0-2
2007-08-05 23:49:57 status unpacked libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:57 status half-configured libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:57 status installed libgnomeprintui2.2-0 2.18.0-2
2007-08-05 23:49:57 status unpacked libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:57 status half-configured libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:57 status installed libgsf-1-common 1.14.5-0ubuntu1
2007-08-05 23:49:57 status unpacked libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:57 status half-configured libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:58 status installed libgsf-1-114 1.14.5-0ubuntu1
2007-08-05 23:49:58 status unpacked librsvg2-2 2.18.0-1
2007-08-05 23:49:58 status half-configured librsvg2-2 2.18.0-1
2007-08-05 23:49:58 status installed librsvg2-2 2.18.0-1
2007-08-05 23:49:58 status unpacked librsvg2-bin 2.18.0-1
2007-08-05 23:49:58 status half-configured librsvg2-bin 2.18.0-1
2007-08-05 23:49:58 status installed librsvg2-bin 2.18.0-1
2007-08-05 23:49:58 status unpacked bootchart 0.9-0ubuntu7
2007-08-05 23:49:58 status unpacked bootchart 0.9-0ubuntu7
2007-08-05 23:49:58 status half-configured bootchart 0.9-0ubuntu7
2007-08-05 23:50:24 status installed bootchart 0.9-0ubuntu7