This may not be very encouraging, but return the printer if you can. I work in computer sales and I cannot stand Lexmark!!! People that use Windows have nothing but problems with them, never mind people that use Linux. Not too sure about Macs, I actually come across more Linux users at work than Mac users.
They also break easily. Stick with HP for all-in-ones in my opinion. Actually, no, stick with HP for everything (although Samsung and Brother are also good for their lasers)
Personally, I use a Samsung ML-1710 Laser printer. (It has now been discontinued and the new ML-1740 has been released, but they are almost identical). Works beautifully under Linux and Windows. Never have any problems with it (except for under Linspire when I tried it at one point to be quite honest) (Debian also chokes on it but Samsung's linux installer works on Debian but doesn't work on Linspire).
Anyways, just my opinion. Sorry to burst your bubble.