I experienced the same thing, printing to a Lexmark Optra M410 via Airport Extreme. I could view the printer, and had no problems printing from some apps (e.g., Eudora always worked), but other apps, no way. My gut feeling was this was, at heart, a PostScript error.
Below is the list of fixes I tried, obtained from a variety of sources, including these discussions.
Sometimes these fixes would work, sometimes not, but increasing the printing memory (#6 below) also seemed to help.
First, make sure you have visited the printer's website and have downloaded and installed the latest print drivers.
If you are using Airport, make sure you have updated to the latest firmware.
1. Repair permissions
2. Delete all printing-related prefs (i.e., "com.apple.print" files)
3. Use Print Utility to reset Print Queue (and then restart BEFORE adding printers)
4. Use a utility like Onyx to clean font and other caches (and then restart)
5. Go into your application's "Page setup" option and make sure that the "Format for" says your printer and not "Any printer."
6. Go to System Preferences -->"Print & Fax" -->"Printer Setup" and increase the memory for your printer. (Mine seemed to default to 32MB. When I changed it to 132 MB -- Voilà.)
Someone also suggested downloading and running Printer Setup Repair:
http://www.macupdate.com/info.php/id/8070 (It didn't help me, but perhaps someone else may find it useful. [Use the "Try it" mode. Then click File Permissions, Printing Reset ....Then click Reset printing system and continue].)
If anyone has tried anything else, please add it to this thread. This problem seems to be causing a lot grief.
iBook Mac OS X (10.4.5) 
