Solution by Anonymous

This was causing NTBACKUP to fail. The resolution was to rebuild the RMS database in Windows by following these steps:

1. Stop the RSM service
2. Delete the RSM databases located at %SYSTEMROOT%\system32\NtmsData
3. Restart the RSM Service, this will create new, empty RSM database

I then re-registered the proper DLL's for VSS:

net stop vss
regsvr32 ole32.dll
regsvr32 vss_ps.dll
Vssvc /Register
regsvr32 /i swprv.dll
regsvr32 /i eventcls.dll
regsvr32 es.dll
regsvr32 stdprov.dll
regsvr32 vssui.dll
regsvr32 msxml.dll
regsvr32 msxml3.dll
regsvr32 msxml4.dll
net start vss

In my case I also had to run before starting the VSS service since this server has MS SQL 2000:

regsvr32 “C:\Program Files\Microsoft SQL Server\80\COM\sqlvdi.dll”