I backup ten Citrix servers, most of the time no problem, even though they do seem to get rebuilt fairly often.
What status codes do your backups fail with?
If status 41, have you tried increasing the CLIENT_READ_TIMEOUT on the media server? This setting controls (in seconds) how long the media server will wait before deciding/concluding that the client is no longer alive/communicating. The default is 300 seconds (5 minutes). If you are getting status 41, try increasing by 300 second increments until the problem is resolved. If you get to 30 minutes (i.e. 1800 seconds) and it's still failing then try the "Status 41 In Depth Troubleshooting Guide", which can be found here using a search: