FYI to all -
The problem appears to be the following:
We were at 9.3 using SDE connections. We upgraded SDE to v10. The service, server name, databases - all remained the same. However, we have to go into our existing .mxds and change all the sources of the feature classes to the same server again. I know, it doesn't make sense.
Long story short - you have to re-establish a connection to SDE 10 if you were at v9.3.
ArcCatalog 10 does not recognize the old connection to the same server.