"all the settings I could think of"
My guess is that there's still one thats being missed. Check out Ian Lyons article
http://www.computer-darkroom.com/ps9_print/ps9_print_1.htm which gives you step by setp the setup for CS2.
If you're using a Windows machine, you can also download a free demo of Qimage which is much frendlier for printing than CS2.