When you SaveAs for the first time, a window pops up for you to choose the location. At the bottom of the window there is a Save As Type dropdown list. What File type is showing in there?

It's a .xlsx file

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?

I've played around with it and it happens whenever I do a save as. Whether I save to the network, my documents, etc.

I'll take a look through that link you posted and hopefully I can figure something out. Usually I remember to close out and re-open Excel after I do a save as, so it doesn't matter too much. But sometimes I'll forget and have to redo everything I just did and it's a pain in the rear if I had done a lot...