Can I get my iPhone to AirPrint to my HP Officejet 6500 E709n
Its not quite AirPrint, but have you tried the official HP ePrint Home &amp; Biz application?

I have it installed on my iPhone and it picks up and prints to HP Photosmart C4500 really easily. Also, installing this application adds a "open with" option when you are viewing a compatible document (pdf/doc/etc) in the web browser / email application etc. That means you just click "open with" then select Hp ePrint and it opens the document straight into the app ready for printing. you even get a print preview as you would printing from your desktop.