We have a history of excellent printing with CS2 and the Epson 3800 with profiles downloaded from the websites of various papers [...] We installed CS4 over the weekend. Nothing else in our workflow is different. But our prints now are muddy and don't come close to what we see on the monitor. [...] Could it have to do with the paper profiles? Do we need to download them again into CS4? The old long list of paper profiles seen to have made the move from CS2 to CS4 automaticallly, but aren't as accurate now.
Sounds like a problem with the colour management settings in Photoshop. Make sure both the working colour space as well as the strategy how to handle colour space misses or mismatches are set the same way as you were used to in CS2. When leaving the colour management of the printing process to the printer then make sure to disable Photoshop's printing colour management (either the printer or Photoshop can manage the printer's colours---but they mustn't do it both at the same time).
The paper profiles usually reside somewhere in a folder determined by the operating system (in Windows XP, it's at C:\Windows\system32\spool\drivers\color), so an upgraded Photoshop version should see just the same profiles the previous version saw. Photoshop can
also store colour profiles in its own profile folder which however is not recommended. If you're storing your papers' colour profiles in the Photoshop-specific folder then you'll have to make sure they got copied to the new Photoshop version's profile folder properly.
-- Olaf