Desativar a impressão bidirecional em sua impressora corrigirá esse problema. Dê uma olhada nisso: Como enviar a impressão para o Windows XP?
Mesmo quando esta resposta se refere ao Windows XP agindo como um servidor de impressão, as mesmas regras se aplicam às impressoras HP quando conectadas a uma máquina Linux. Experimente e por favor informe.
Boa sorte!
Editar:
Além disso, dê uma olhada em HPLIP (o HP Linux Imaging and Printing) . Isso pode ajudá-lo, mas a maioria dos HPs está funcionando perfeitamente, e insisto que você pode estar com problemas de impressão bidirecionais. Infelizmente eu não tenho um HP fisicamente conectado ao meu computador neste exato momento para executar um teste. O HPLIP pode, no entanto, ajudá-lo.