Eric,
You can try deleting the database files associated with CPS and run a repair install:
Stop all CPS services
Goto Program Files\Veritas\Continuous Protection Server\Database
Delete RSA.db and RSA.log (only used for the CPA)
Open Add/Remove Programs and run a Repair install for CPS (this should recreate the db files)
You can say "No" to the reboot and then verify if the services will start.
If this does not resolve then you must Uninstall/Reinstall the CPA
Note** You do not need to perform an upgrade when installing the CPA since the job information is included on the CMS (Continuous Management Server). You can simply uninstall the older version then push out the new version from the console.