Welcome to CA’s forced upgrade hell. If you decide you don’t want to trash it an buy something else, try some of the following:
Make sure the service account is set up properly to log on as a service and that it has at least backup operator priveleges. Try changing the password and then chaging it in the service startup properties.
Check the Windows event log for more info – it may give you a better clue.
Check CA’s support site – the knowledgebase still has Arcserve 2000 info.