Have you tried changing the printer driver
to another emulation(like from ps to pcl vice versa)?
What type of port are you using? Is it the standard tcp/ip or the lexmark enhanced?
There is a network firmware update available on the lexmark website and you can update it using the web interface: Lexmark - United States
Make sure to check the version of your network firmware before you update it. The version on the site is NL.APS.N213e, so if the version you have is not the latest one, you can go ahead and update it. To look for the firmware version, access the web interface, click on Reports tab then choose device information.
To update the firmware download the file first, then extract it. Then go to the printer's web interface, click on settings, then update the firmware.