I had more or less the same problem with my HP printer.I have a USB-connected HP laser printer. Under Fedora 10 and CUPS everything worked fine. Except occasionally (after hibernating) CUPS would think that the printer was of line. Unplug/replug of the USB connector solved the problem.
I deleted the printer and then reinstalled it using the cups interface (http://localhost:631/). Now it works fine. I don't know what was causing the trouble.
Hope this helps.