There's a long article of problems/fixes around saving Excel files here:
http://support.microsoft.com/kb/271513

I scanned through it but none of the symptoms on there seem to precisely match yours. Worth a look though in case something stands out at you.

When you do the first saveas to another location, is that other location a local drive, a network drive, etc..? Does it make any difference if you vary it, or does the problem repeat wholesale no matter where you saved the file?