HP Deskjet 830C Printer Problems on Macintosh OS 10.4.X

So I have a HP Deskjet 830C which has been a great printer for us for some time. Recently I got a new MacBook Pro (which I love) and decided to get an Airport Express wireless adapter which also has a USB print server built in. It rocks as well.

However, every once and a while, my new MacBook goes to print (here's a sample document) and gets the following type of output. It looks like the text is twice as large as it should be but only the first 1/2 of every line is being printed. Somewhat useless to say the least.

bad printer output

However, my Mac G5 desktop box downstairs prints fine to the device every time. One interesting point of order is that my G5 is using HP Printer Driver 2.7.1 while my MacBook is using 3.3.

Aha! Non-Black is Not Affected!

So in printing out the web page (see here), I noticed that the blue text links seemed to be fine while the rest of the black fonts looked double-high/cut-off.

NY Times Bad Output

Another round of printing of colored output seemed to back up that only black text was affected.

Color output ok

What We've Tried

Here is what I have done to try and fix the problem:

Free Spam Protection   Eggnog Recipe   Android ORM   Simple Java Magic   JMX using HTTP   OAuth 2.0 Simple Example   Great Eggnog Recipe