I've finally solved all the issues with PackageKit and Debian - I present the new gnome-packagekit frontend for Debian:

Joking aside, Debian and Ubuntu can work just fine with PackageKit, I'm really not sure what all the noise is about.