That'll teach me to read the footnotes first - I've always read
that page as meaning that this or that function was/was not supported by
HPLIP - it seems a bit redundant to me to do otherwise ('Yes, I already
know that my OfficeJet 6310 has a network port and can print, scan and
fax.')

Thinking a bit harder about the problem (yes, it *does* hurt, thank you
for asking) - David says he tried to install his printer through
System>Administration>Printing. Can I ask, have you tried using
hp-setup to install the printer? This method seemed to work better for
me - I had some problems with my DeskJet 840 after installing through
Sys>Admin>Print which were cleared up after using hp-setup.

Also, I had a similar problem yesterday in that my PC decided to stop
printing to both my 840 (USB) and my 6310 (Network). In the end, I had
to reinstall HPLIP to get them working again.