Eu tive o mesmo problema com a minha Deskjet d2660. A solução foi baixar e instalar os drivers mais recentes diretamente do site da HP.
O diálogo de download pode dizer-lhe que o Ubuntu já tem o driver correto para a sua impressora, no entanto, faça o download e instale-o mesmo assim.