Cannot install libxml-simple-perl

Kubuntu 12.04.1

The only additional repository I have is for virtualbox-4.1. I also have the partner repository enabled.

I have run apt-get update, apt-get upgrade, and apt-get dist-upgrade. These report my system is fully up-to-date. I have also run apt-get -f install and nothing was done.

I have no logs in /var/log/dist-upgrade. The logs in /var/log/apt show no errors.

However sudo apt-get install libxml-simple-perl returns:

phl@vid:~$ sudo apt-get install libxml-simple-perl
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 libxml-simple-perl : Depends: libxml-sax-perl but it is not going to be installed
                      Depends: libxml-libxml-perl but it is not going to be installed or
                               libxml-sax-expat-perl but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

If I try to install all of libxml-simple-perl, libxml-sax-perl, libxml-libxml-perl and libxml-sax-expat-perl, I get

The following packages have unmet dependencies:
 base-files : PreDepends: awk
 libc6 : Depends: libgcc1 but it is not going to be installed
         Depends: tzdata but it is not going to be installed
 libxml-libxml-perl : Depends: libxml2 (>= 2.7.4) but it is not going to be installed
                      Depends: perl (>= 5.14.2-6ubuntu1) but it is not going to be installed
                      Depends: perlapi-5.14.2
                      Depends: libxml-namespacesupport-perl but it is not going to be installed
 libxml-sax-expat-perl : Depends: perl but it is not going to be installed
                         Depends: libxml-namespacesupport-perl (>= 0.03) but it is not going to be installed
                         Depends: libxml-parser-perl (>= 2.27) but it is not going to be installed
 libxml-sax-perl : Depends: perl but it is not going to be installed
                   Depends: libxml-namespacesupport-perl but it is not going to be installed
                   Depends: libxml-sax-base-perl but it is not going to be installed
                   Depends: ucf (>= 0.28) but it is not going to be installed
 libxml-simple-perl : Depends: perl but it is not going to be installed
                      Depends: libxml-namespacesupport-perl (>= 1.04) but it is not going to be installed
 linux-headers-generic : Depends: linux-headers-3.2.0-29-generic but it is not going to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.

I checked linux-headers-generic and linux-headers-3.2.0-29-generic; they are both installed. Perl itself is obviously also installed and is at version 5.14.2-6ubuntu2.1. libxml2 is at version 2.7.8.dfsg-5.1ubuntu4.1.

This is a reasonably fresh install of 12.04.1 from just the past couple of weeks