You're running Photoshop in Classic? 😱
I strongly suspect it's a permissions thing. We had a problem with Photoshop CS recently on one of work machines when it wouldn't save to the desktop... repairing permissions fixed that.
It could also be a journaled disk-thing, but that's just a guess and probably not likely...
Question: Does it do this consistently, no matter where you try and save the document? Just as a test have you tried saving it to 'root' level of the hard drive i.e. the first level of the HD outside all the system and users folders?