OS X printer hell

I cannot get an HP Deskjet 812C printer to work with a Mac. What I've
tried:

- Network printing to CUPS on Linux box: Used to work, sort of. The
printer would often "jam". There's a button on the printer with an
amber LED on it, next to a paper feed logo. This light would flash,
and printing would resume when I pressed this button. I figured
things would improve if I cut out the Linux box.

- USB connection to iMac running Tiger: Lots of garbled
pages. Non-garbled pages often have weirdly scaled fonts, with letters
stretched out, and tops and bottoms truncated. I thought for sure this
would just work. But no.

- USB results were so bad that I'm going back to network
printing. Now, the job doesn't show up on the cups printer queue. On
the iMac, I get a "Jobs stopped" message from the printer utility.

It shouldn't be this hard to print, especially on a Mac. What am I
doing wrong? The printer is only 2-3 years old, maybe a little older
than the iMac, which is running Tiger.

Help!

Jack Orenstein