Comprueba que tienes instalados los paquetes
foomatic-db-hpijs y
hplip-ppds. Por cierto, en tu primer mensaje dices que hiciste un "
apt-get install hplip" y nada... ¿A que te refieres? ¿A que no encontró el paquete? Si es así te digo que según
ésto el paquete está contenido en los repositorios
universe de Ubuntu.
¿Miraste ya los logs?
Saludos.