I have the Lexmark P3120 AIO, and for the longest time I could never get it working in Linux. Well, I finally figured it out (printing only), when I saw that the P3150 was confirmed working and I was only 30 model numbers behind. I used the Z600 drivers for Linux that were provided by Lexmark. Lexmark’s Linux driver support is halfhearted and incompleted, but the Z600 driver works for a wide range of Lexmark printers.
To check if your printer will work either with the Z600 or Z700 drivers, consult Gentoo’s Lexmark Printers guide.
If you’re using Gentoo, well lucky you. Just follow the instructions on the Z600/Z700 ebuilds there.
If you’re using RedHat, it’s even easier. Get the Z600 RPM provided by Lexmark.
If you’re using Ubuntu, there are guides for Breezy users on the Ubuntu website:
Ubuntu Wiki guide
However, I prefer the Honey Badger IT guide. Keep trying until one of them works for you. I think using alien to convert the RPM to a .deb is the best way (look on the guides!).
Edgy users will need to copy the PPD from the driver (after following one of the above guides, that is!) to /usr/shared/ppd, because that’s where CUPS looks for the PPD in Edgy.