Yo instalé hace nada mi HP DeskJet 840C (usb), así q supongo que muy diferente no debe ser la cosa. En mi caso lo hice con CUPS, el paquete cupsomatic y los drivers de Gimp (todos estos paquetes están disponibles en sid y supongo que en woody, en potato ni idea...) y va perfecta. Si además instalas webmin-lpadmin puedes hacer la instalación desde una interfaz web la mar de simple y agradable. Espero que te sirva.