Download the latest version of HPLIP from http://sourceforge.net/projects/hplip/files/ (forget the ubuntu standard repository)
Preferably set the printer to a static IP (using the small display and some tiresome typing)
Install the following packages:
python-qt4 python-qt4-dbus libsnmp-dev libsane-dev libcups2-dev libusb-dev python-dev
Run the hplip-x.xx.xx.run from the commandline. Choose the automatic install option.
When the installation is complete and the automatic configuration window pops up, set it to pick up the ip address of the printer (I think you have to click the ”advanced” button for that). Click ”next” till you are done.
The system administration “Printing” option is junk for installing a HP printer, even if you give it the IP address or whatever. I think it is due to the difference in “Device URI” which in my case ought to be ”hp:/net/Officejet_4500_G510g-m?ip=192.168.1.219”