If you look in the backup selections does it still show the server by the old name or is it showing the new one? Try switching to the Text view and see if there is an entry for the old server and if there is remove it from the selection list.
Once you've confirmed that all references to the server in the selections list are using the new name, if it still shows up using the old name in your job log then you might want to try re-installing the remote agent from the remote server, and see if that makes a difference.