Linux and Lexmark printers

Lexmark, supposedly, has Linux-compatible setups. However, I recently had no luck with installing a Z810 color inkjet with the Mandrake Linux 10.1 OS. I tried everything I could find on the web and nothing worked.

Then, I took an HP 712C off of another machine and it went like a champ.

Has anyone else had problems getting Lexmark printers/devices to work with Linux?