I would at the least upgrade ArcGIS Desktop to v10.1 on the ArcGIS Server (AGS) machine so you can administer services. Then upgrade on that machine. I would then upgrade the remaining desktops. Then finally I would upgrade SDE.
What type of connections do you make to SDE (service or direct)?