Funcionou no ubuntu 10.10 e fiz da seguinte maneira:
1- desinstalei todos os pacotes que tem no nome hplip, isso pelo Gerenciador de pacotes Synaptic;
2- reiniciei a máquina e instalei o pacote
http://launchpadlibrarian.net/33367916/hpijs-ppds_3.9.8-1ubuntu2_all.deb, no caso, baixei o pacote e depois com o botão direito >Abrir com Central de programas do Ubuntu e instalei;
3- Depois no terminal com root, digitei o comando: hp-plugin -i, que vai instalar o PLUG-IN INSTALLATION FOR HPLIP 3.9.4b e na opção Enter option (d=download*, p=specify path, q=quit) ? digite d, no final disto confirme com y (sim) no procedimento da instalação;
4- reiniciei a maquina de novo, por conta do cups;
5- De volta, fui em Sistema / Administração / Impressão e cliquei com o botão direito >Propriedades, e ir em fabricante e modelo clique em >Alterar;
6- Escolhi o fabricante HP e modelo da impressora deskjet d2600, na parte drivers escolha a opção com HP Deskjet Series hpijs, 3.9.8.36 [en],, avancei e usei a opção >Use o novo PPD e depois em >Aplicar.
7- Dei reboot terminal como root, e protinho para usar.
ps.: funcionou na HP PhotoSmart C4200 series também!
Espero ter ajudado.