I tried all of your remedies shown here and still couldn't print.

I have a brand new iMac, the Linksys wireless G printserver WPS54G, and my printer is a Xerox Phaser 6120.

Here's what finally worked...

On the dock, click System Preferences
In the next window, click Print & Fax
Click the "+" button to add a printer

Another window opens up.
Click "AppleTalk"
Wait a moment while your Mac sniffs the airwaves and if it "sees" the printserver, here's what will appear in the panes in the same window...

In the left pane, you'll see "Local Zone"
In the right pane, you'll see words, letters or numbers--this is the NAME of your WIRELESS PRINTSERVER!
Click on that name to highlight it.

Immediately, you will see at the bottom of the window, a spinning icon and the words "Sending data". I sat there until I was practically hypnotized and nothing else happened. If this happens to you, go upstairs or wherever that dang printserver is, and unplug it from the wall and from the printer.

Wait 30 seconds, plug it back to the wall, then back to the printer.

By the time I got downstairs, the spinning icon and the offensive words "Sending data" were gone.

Leave the Name and Location alone -- do not change this because I don't know what will happen!
In the box that says "Print Using:", click the up/down arrows and you'll see three choices.

Click on "Select a driver to use.." and it will open a dropdown box with all the driver choices. Type all or part of your PRINTER name (NOT printserver name) into the box until you find your driver. Click on it. Then click "ADD".

If your printer has options such as a duplexing tray, you may get another window asking if the options are installed. Check or uncheck boxes as needed.

This should do it for you -- try to print. If not, muttering dark and angry words and throwing things at the cat helps for a short time.