This is similar to the fix another poster mentions above, but will leave you with the latest working Lexmark driver rather than the version on the Lexmark website (which will likely be older than the version you receive through software update).
My only solution to this problem on my Lexmark x9575 (connected to my network by ethernet) was to revert to the 2.3.1 Lexmark Drivers and ignore the 2.4 update which breaks printing on all of my Macs. This involves:
1) uninstalling the drivers from the link in the folder within Applications or on your desktop (mine is called Lexmark 9500 Series and it lives on my desktop);
2) Go into the Library folder on your main hard drive (NOT within your user folder, the hard drive is usually listed in the finder as Macintosh HD unless you have renamed it) and delete InstalledPrinters.plist and the Lexmark folder (restart after uninstalling the driver in step 1 if it won't let you do this);
3) Download the latest drivers for your model on the Lexmark website and install them;
4) Search on the internet for 2.3.1 Lexmark Printer Driver. At the time of posting you can find it here:
http://mac.softpedia.com/get/Drivers/Apple-Lexmark-Printer-Driver.shtml
5) Check you have version 2.3.1 - it should be called LexmarkPrinterDrivers2.3.1.dmg and install it.
6) go to software update, which will prompt you to install the 2.4 drivers and set software update to ignore the update (this can be done by clicking on the name of the update to highlight it, then going to the Update menu and selecting Ignore Update).