Try restarting the Map Service after changing the source data if it is Dynamic Map Service, while for the Tiled services you need to obviously create tiles again.
For Feature Services restarting might not be required as I have not tested it.
Point is try restarting the service. It works for me.
There is an option to overwrite the existing service.
You can change the data sources in your mxd. Then when publishing, choose to Overwrite an existing service, rather than publishing a new service. You will not have to delete the existing service, and overwriting maintains all of the settings in the service.
Jennifer's answer is right. I found it to be the easiest way to update data sources or other properties of a service. See also: Overwriting a service in ArcGIS for Desktop—Documentation (10.3 and 10.3.1) | ArcGIS for Server
However, things usually get complicated with tiled services. In theory it should work as the help says - if you keep "Update cache automatically", the server will be busy for some time bit it should deal with it. In practice though, I always run into difficulties with updating cached services and then spend long time fixing it. If you have any tips, please let me know.
I use 10.2.2
What kind of difficulties do you run into? Have you tried not updating the cache automatically, and then manually starting caching once the service has been overwritten?
The issue I am dealing with at the moment appears to be similar to this:
When I left "Update cache automatically" ticked while overwriting the service, I can then see my CPUs work harder. Once the CPU load drops again (caching has finished) and I preview the service, some tiles were obviously missing (HTML Error 404).
I then tried to re-create the tiles using Manage Map Cache Tile tool but it errors out saying:
Output failure, error string = Error moving bundle
Failed to cache extent:...
and then it repeats for each process (i.e. each CPU that worked on it).
I've had the error "Output failure, error string = Error moving bundle... Failed to cache extent:..." before. In my experience, I have found that this is usually due to a corrupted bundle and will persist in that service until the specific bundle is deleted through windows explorer, and then re-cached. Otherwise it would error out every time we cached an area in that specific bundle and scale. This could be the problem, not actually the service overwrite causing an issue.
If it is the service overwrite causing an issue when the service has the Update Cache Automatically option set, i would recommend setting it to Manual when overwriting the service. Then running the cache generation separately. Maybe something happens on the back-end that corrupts the bundle when you overwrite with the Automatic option set?