Hi,
Have you tried creating an altogether new job for the media server?
Please read:
How to delete a machine that is no longer on the network from backup selections, so that the backup job does not end with error "The Media Server was unable to connect to Remote Machine . The machine could not be found on the network."
http://support.veritas.com/docs/271379
Regards
Padmaja