Before printer setup, be sure to have all the following already installed:
- cups
- foomatic
- hpijs
- hplip
- foomatic-db-hpijs
I could be forgetting something, here are the install instructions given by hp which worked for me:
http://hpinkjet.sourceforge.net/install.php
I don't know what repositories you are using, but all the necessary is in debian's so you don't need to download and install anything from the hp site.
The printer works very good in Linux and you can even calibrate or clean cartridges with the tools given by hplip, keep on trying.