What you probably want to do anyway is do a save as not a save.
I personally do not think it is a smart approach to do a save on top of opening a legacy file, IMO.
Doing a save as does two things to your advantage one it will probably make the file size a bit smaller and two it i=will overwrite some of the out of date
data in the file and you will always have the original.
Try doing a save as.
Have you changed your Document colour mode to CMYK first ?
As Wade said, use a Save As.... The issue is either due to the original file being locked in some strange way, either on the file system level or in its internal data structure, or you requiring to indeed adjust a few document options to make it compliant with CS4. Fil's guess about the document color mode is a good place to start and you may need to checkk additional options for richt blacks and color profile conversions...