I just had the same problem (also KPackageKit on 11.04), the only workaround I could find was to do a "sudo apt-get upgrade" on the terminal, to get at least the necessary updates done.
I just had the same problem (also KPackageKit on 11.04), the only workaround I could find was to do a "sudo apt-get upgrade" on the terminal, to get at least the necessary updates done.