Bruck,
Take a look at my reply to the topic "epson 3800 heavyweight matte paper color issues."
You may have a hardware, not a software problem. You describe the prints I had gotten from Photoshop CS3, or CS2 on my 3800 until I decided that the printer was laying down too much Cyan and Magenta ink, muddying the reds, blues and greens. I think this may be how they are setting the current crop of 3800's (or else they are sending them out uncalibrated). Try printing from the Epson driver instead, telling Photoshop or Indesign to "let printer manage color" after converting the image to the profile you've gotten for the paper. Play with the "custom, advanced" settings in the Epson printer driver to reduce cyan and possibly magenta, and give it a little saturation boost to compensate. I'm guessing that you will say you didn't know the printer could print that well.
Besides the method I mentioned in the above referenced reply, it may be possible to recalibrate your printer using ColorBase (available as a free download from the Epson UK site), provided you have access to an Eye-one spectrometer or know someone who does and who will help you out with the readings. It will require reading calibration patches for each Epson paper type you use (use only Epson papers to calibrate the machine). I haven't tried it yet, though, as my work-around seems to be doing just great. It may not be the "pro" approach, but it works.
It's a great printer when you figure it out and make the appropriate adjustments.
Good luck and Aloha,
Aaron