Small miracle: the Xerox Phaser 6130n that I bought works with Linux.
My version of Ubuntu (8.04) didn't want to support it initially. It didn't have a driver available and recommended a driver for a different Xerox model. That did not work. It spat out a few pages with gibberish on them instead of a test page.
I grubbed around on the CD that came with the printer and found a directory named "Linux". What? A major manufacturer supplying something for Linux right out of the box? Great! But what was in there was a .rpm file for a driver. Ubuntu doesn't use .rpm files for packages, it uses .deb files.
There is a way to convert between .rp and .deb package formats, and I started down that path, but simultaneously I went to the Xerox web site to see what they had out there. I hoped they'd have a pre-built .deb file I could download, since Ubuntu is pretty popular.
What I found, though, was a bit different. They had PPD files available, and PPD files allow the CUPS system to work with a printer just like a driver does. (Or so I gather, since my choices were to install a driver or a PPD file.)
So I downloaded the archive full of PPD files, extracted the one for the 6130, and installed it.
Like magic, the printer worked. It prints in color, prints images, etc. This is great news.
Every ink jet printer I've ever owned has ended its life with print heads full of dried up ink that will not be removed and prevents clear printing. The most recent one, while it was suffering from a clogged print head too, actually died a horrible mechanical death when something went "POP!" inside it one day. It never printed again.
I hope this new Xerox 6130 works out well. I've been without a printer for months now, trying to figure out what laser printer would work with Linux.
So far, so good!