I've just spent an annoying two days trying to un-break my HP multifunction printer/fax/scanner, and I hope I can spare some of you the same trouble.
My symptoms were that I couldn't send a fax using hp-sendfax, which has been working very well for years -- until now. After much floundering I finally tried deleting my existing cups printers and allowing hp-setup to create new ones. All better now :) There may be more than one way to delete cups printers, I dunno, but I used the cups http interface by typing 'http://localhost:631' in my firefox URL bar (cupsd must be running for this to work).