I have experienced exactly the same problem with a new 11" Macbook Air and a Lexmark C544 printer, even though other Apple computers on the same network and running the same software with the same version of the printer driver worked fine.
Although Apple were quite unable to help, my local expert (Graham Letts of Icon-Digital) solved it.
Go to add the printer but ignore the Lexmark printer which it offers. Go to add an unspecified printer; it will again offer the Lexmark but ignore that too. Click on the IP tab and enter the IP address of your printer. Continue with adding this, and it works!
While the printer will appear by the IP address as its name, you can change this to something more aesthetic if you wish, later.
Hope this solves your problem too.
Try to delete the Lexmark print queue under Print & Fax / Print & Scan then manually add a print queue. Steps here: http://bit.ly/TdUuHL
If it doesn't work, reset the printing system: http://support.apple.com/kb/HT1341 then add another print queue manually.
Also, check for a software update for your Lexmark printer.
I had the exact problem with my Macbook Pro Retina and Macbook Air. Followed your guys instruction, it finally works. I need to mention one thing to anyboy following me. During the manu setup, after input IP address, you need to pick Protocol HP JetDerict-Socket. I picked the IPP protocol first. It did not work. Thank you guys.
It is good of you to take the time to post here. The following is intended as "constructive criticism", not as an attack.
The add-a-Printer document you pointed to gives three different procedures, depending on how "smart" the printer is, and how it is attached.
It is easy for an unsophisticated Reader to assume that the procedure you intended is the first one (of three) listed. That would NOT allow this (smart, Network-attached) Printer problem to be solved successfully. The idea that you provided a document with three procedures in it, and intended the Reader to find the SECOND one, may be lost without Specific Guidance.
Many Readers seem to find the nuances between different smartnesses and attachment methods of Printers baffling, and that can be a LOT of the problem.
Printer Manufacturers need to thump on the concept that Network Printers are Vastly superior (and that is why they cost more), but attach differently and use the Drivers differently. One size Driver does not fit all.
Oh my effing God! For over 6 months, I have been trying to solve a similar issue with my new MacBook Pro not printing wirelessly to my Lexmark E260dn while my iMac and Air had no problem at all. I am so glad I Googled "ipp-missing-job-id" and found this thread.
It never occurred to me to add the printer manually using the IP address -- and I'm pretty experienced with this kind of troubleshooting. I guess I am so used to expecting our hardware and peripherals to automatically find and connect to each other that we forget that there can be errors like this and we have to do things manually.
Thanks so much jgbeaumont and to "Graham Letts of Icon-Digital". I learn something new everyday!