E: Internal Error, Could not perform immediate configuration (2) on perl

Binary package hint: perl

Trying to upgrade from karmic to lucid today, I got the following error:

# apt-get install perl
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  linux-headers-2.6.31-13 libusplash0 libntfs10 libgnome-mag2 dvd+rw-tools mesa-common-dev
  gobject-introspection gnome-volume-manager human-icon-theme tix ntfsprogs tablelist libscrollkeeper0
  nautilus-sendto sound-juicer
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
  libdb4.8 libperl5.10 perl-base perl-modules
Suggested packages:
  libterm-readline-gnu-perl libterm-readline-perl-perl
The following packages will be REMOVED:
  perl-doc
The following NEW packages will be installed:
  libdb4.8
The following packages will be upgraded:
  libperl5.10 perl perl-base perl-modules
4 upgraded, 1 newly installed, 1 to remove and 1778 not upgraded.
Need to get 0B/9,489kB of archives.
After this operation, 11.6MB disk space will be freed.
Do you want to continue [Y/n]? y
E: Internal Error, Could not perform immediate configuration (2) on perl

Same thing happens with "apt-get dist-upgrade" (which I tried first of course).

$ apt-cache policy perl
perl:
  Installed: 5.10.0-24ubuntu4
  Candidate: 5.10.1-8ubuntu1
  Version table:
     5.10.1-8ubuntu1 0
        500 http://archive.ubuntu.com lucid/main Packages
 *** 5.10.0-24ubuntu4 0
        100 /var/lib/dpkg/status