Algumas impressoras HP estão caindo num bug do hplip instalado no Ubuntu 10.04.
Experimente baixar o hplip correspondente a sua impressora do site da HP. Ele vem em .deb e é só clicar nele duas vezes para instalar.
Eu fiz este procedimento e funcionou para mim, mas ontem entrou uma atualização do hplip dos repositórios aqui na minha maquina, eu instalei mas ainda não testei.
[],s