Verifica se o pacote "hplip-cups" está instalado. Experimenta também instalar o "hplip-gui", que é um utilitário de configuração de impressoras HP. Se isso não funcionar, sugiro reinstalar o Ubuntu 12.04 do zero, sem atualizar de versões anteriores (atualizar é um procedimento mais fácil, mas costuma dar certos problemas) e instalar pelo menos o "hplip-cups", que é o driver de impressão genérico para Linux da HP.