I can understand your problem but its difficult to find the root cause without seeing the logs.
What i suggest:
1) You have said that BE 9.1 works good with win 2k3 but 10.0 dosent.
a) Check for any MDAC disripencies (Mismatch DLLS).
Component checker.
http://www.microsoft.com/downloads/details.aspx?FamilyID=8f0a8df6-4a21-4b43-bf53-14332ef092c9&DisplayLang=en
Here are the steps which you may follow:- -Run component checker. Select the first option to determine release. Click yes.
-Select the second option, but select the version identified in the first option.
-Under file details you should see a Match if everything is correct otherwise you will see a mismatch DLLS.
If there is any mismatch dlls, replace it with the expected versions from another server and try to start the services.
Finally,
Is Backup Exec using existing SQL instance, incase yes, Try installing the Backupexec with a separate MSDE instance.
Keep updated.