Hi Tamadie,
If I add a new layer to a map that its load in an application, and then rewrite the service, the application when refresh it has the new layer. There are some issues like symbology, that I need to remove and then add it again the map service en the application, but not new layers or data changes.
If you work with 10.1 server you just has to re publish the service with the option overwrite an existing service.
When we have 10 server we need to re start the service and clear the cache. Sometimes the order of the steps just commented can give you trouble. Try to check the service directory to see that the service effectively change, then refresh the application. Last step if the service change but the application did not, should be to remove and add the service in the viewer again.
Hope it help.
Regards, Manuel