Make sure that the subnet is correct on you Lexmark printer...
Make sure you can ping your priner.
Also you might try to kill the lpd and then restart it....
As root do ps -aux |grep lpd
kill any lpd processes (be careful not to kill yourself)
then do "lpd" to restart the lpd.
I have a lot of experience networking Lexmark 6XX printers so if you can't get it working send me a copy of your "Print Menus" and "Print Net Setup" pages off of the printer and I'll see what I can find.
Also Lexmark has a printer manager for Linux which can configure, autofind, and install printers onto your system. You can download it at
www.lexmark.com.
Good luck!