I, too, just renamed our backup server (new server naming structure) and wish I'd found this before emailing support for such a simple fix.
Support only told me to change HKEY_LOCAL_MACHINE\SOFTWARE\VeeaM\Veeam Backup and Replication\SqlServerName. I did that, and backups started running again.
But I found this thread just now, and took it a step further: I just searched the entire registry for the old servername and found it lurking in many places...both VBR and non-VBR related. Changed it everywhere and rebooted, and now I'm confident the name has been changed for sure.
I would suggest everybody who has renamed their server do the same!