Sorry for you. You haven't been the first to get burned by Lexmark's crappy Linux support.
These modern el-cheapo printers are like Winmodems or software modems. Used to be that printers had to have complex hardware and embedded proccessors to be able to take postscript or pcl and turn it into print and then to also control the head on the printer and such. Nowadays these printers use your system's cpu to emulate this functionality and require complex drivers to control it via the usb connection. These drivers are generally propriatory.
Probably they can be made to work with Ubuntu. See here:
http://www.linuxprinting.org/show_printer.cgi?recnum=Lexmark-Z22
Ubuntu by default, like all modern Linux distros, use CUPS (common unix printing system) to print. This is used by Linux and a wide veriaty of other systems such as OS X. This is designed to fix most of the printing issues Unix systems traditionally had.
This propriatory Lexmark driver is designed to use the relatively obsolete lpd method. You can try using the driver and install lpd and uninstall cups.. or better yet try that guy's "lexmark foomatic kit' to get it working. Should work with most 'Z' series printers.
If either method doesn't work then your SOL.
For future reference the printers to buy are either Epson or HP printers generally. Stay away from the cheapest printers of all brands if you can.
Recommended printers are stated here
http://www.linuxprinting.org/suggested.html They are based on compatability, quality output, and ink usage.
And a attempt to keep printer compatability database is aviable at
http://www.linuxprinting.org/database.html
Hope that helps in the future.