I think a lot of the strangeness and mixed reviews you see on wireless print servers comes from the fact that people are hooking them up to basic desktop printers which really aren't intended to be networked (not to mention wirelessly). That's why, as
Arcanedeath pointed out, about the only thing you can count on are printers with built-in wireless connectivity.
I've been there. I've gotten print servers and hooked them up to nice printers and things work great for the most part, but you'll usually have little annoying problems. Even expensive print servers seem to take a big crap when you try to print something now and then and need reset every couple weeks. I have an HP hooked up to a wired print server that likes to flash its lights about half the time you print something then will start printing just fine once you hit the form feed button.
In my experience I have to say it's just not worth it trying to network a printer that didn't come with networking capabilities. It's caused me a lot of headaches and wasted money. I'd really like to try something like a Netgear ProSafe, but it's $140. You're basically paying an extra $100 for the print server (and it doesn't have the parallel port you want):
http://www.newegg.com/app/ViewProductDesc.asp?description=33-122-025
You can find a printer with built-in wireless for under $200. I guess it's a bit of a toss-up. The bottom line is that you can't be sure if your printer / print server combination will work until you actually try it, so getting a wireless printer is a little safer.