Parece que uno de mis karmas es instalar impresoras en Linux.
En la tarde compré una HP Laserjet P1005 para imprimir mi tesis. Al conectarla a mi Dell con Ubuntu 8.10 me recibió con un hermoso mensaje de "Configurada para imprimir", pero no funcionó nada al tratar de imprimir.
Lo primero que me funcionó fue instalar hplip-gui y correr

sudo hp-setup

Instaló el driver hpijs correcto para la impresora y comenzó, al fin, a imprimir. El problema fue que la impresora se volvió errática. Me di cuenta que, por ejemplo, con Evince y Okular la impresora se bloqueaba, cosa que no pasaba al imprimir con xpdf.
El driver con el cual Ubuntu viene por defecto es foo2xqx. Desinstalé la versión de Ubuntu, fui a la página del driver foo2xqx, lo descargué y seguí las instrucciones de instalación. ¡Eureka! Ahora sí funciona como corresponde, con los distintos programas.
Síntesis: Desinstalen la versión de foo2xqx que viene con Ubuntu 8.10, descarguen y compilen la versión del sitio de origen