Long time ago, I used ArcServe. I loved it. Especially how it stored the database of files backed up and how it let you look at a single listing of files on a given disk and pick the version you wanted.
We ended up switching because a Dell Consultant had us switch after we started have seriously slow backups - which, months later we found out was attributed to corrupt or bad SCSI drives and had nothing to do with ArcServe. But by that time we had made the switch.
ArcServe support was nothing special... but not horrible as I remember it. BUT, that WAS YEARS ago.
Veritas was fine... we started with 8.6 and tried to go to 9 - that was awful. 9.0 had more bugs than a swamp. And even the Veritas techs new it - on my calls I asked them if they were getting more calls than usual for a new product and they admitted they were. I left the company before 9.1 came out, but MAYBE it's ok now with 9.1 and 10d. My biggest problem with Veritas today is that it's owned by Symantec - a company that hasn't made a decent product in well over a decade.
At this time - based on what others say about CA, I would have to say your damned if you do, damned if you don't pick one of them.