Solved! Go to Solution.
Simply updating the mxd will not update the service.
I believe that you have to literally overwrite the service, i.e. republish it.
Here is a related discussion:
http://forums.arcgis.com/threads/73931-Problem-updating-a-service-created-from-an-.msd
As Anthony mentioned, you'll just have to restart your service after saving the mxd, not trying to re-publish the service with the same name. In addition, you might have to login to the REST Admin if you're not using ArcGIS 10.1 yet (http://yourmapservice/ArcGIS/rest/admin) and clear the cache. See here for more information.
Jamal,
You are using 10.1 and I don't believe that you need to clear the cache.