I had similar printing problems with 3 different HP printers, either not printing reliably or not printing at all. This is on several different PCs, 3 different printers: HP 4L, Deskjet 855c, Deskjet 722c, using both USB and parallel.
The solution above and several other solutions on this forum have not worked for me. I have been experimenting with other distros and found Mepis to work flawlessly. I had hoped Ubuntu 6.06 would improve over 5.10 but this did not happen.
In frustration I closely compared Mepis to Ubuntu and found several differences, mostly in terms of the config files used by cups. To make a long story short, the silver bullet is literally to blow away the Ubuntu /etc/cups directory and replace it with the contents of the Mepis /etc/cups directory. Ubuntu now prints like a charm because cups is being properly initialized. Bottom line: Ubuntu's cups config files are junk.
Specific steps required are:
1. As described in /usr/share/doc/cupsys/README.Debian file, you need to add the user 'cupsys' to the group 'shadow' using this command: sudo adduser cupsys shadow.
2. If you have not already done so, you need to create a full root account using this command: sudo passwd root. When prompted, enter your current password (the first user account created on the machine), then the new password for the root account.
3. Get yourself a copy of Mepis. A free download. Boot it up, As root, tar up Mepis /etc/cups directory including all subdirectories, and preserving all paths. Email the gz file yourself to get them off the Mepis box and into cyberspace, On Ubuntu, retrieve the email with the tar.gz file and save the file to the Ubuntu machine. As root, extract the files from the tar and extract to the Ubuntu /etc/cups directory, overwriting all the contents.
4. Re-boot your machine to restart everything, or simply restart cups itself: 'sudo /etc/init.d/cupsys stop', and then 'sudo /etc/init.d/cupsys start'
You can now open the CUPS web admin interface (http://localhost:631)
, add a printer, authenticate as root using your root password when prompted by CUPS, and install the printer.
Basically all I did here was set up required permissions that cups has disabled by default (and that are documented in the readme cited above), and change out the cups config files (there are several, not just cupsd.conf) used in Ubuntu for the cups config files used in Mepis, and everything works. FINALLY !! after only 4 months of putzing around.