Cannot use this feature without credentials

[Coletrain]

We lost the Domain Controller that was hosting the RMS services (despite the
recommendation not to put it on a DC - I wasn't around for the initial
installation)
It was rebuilt, and RMS appears to be set up correctly with the original
DRMS_Config database.

We are trying to recover some protected files that were created before the
rebuild, but get the “Cannot use this feature without credentials” error.

This is what’s being used:
Windows 2003 server
RMS 1.0 with SP2
Windows XP Pro with SP3
RMS client 1.0 with SP2
Excel 2007

The only warning I get from IRMCheck is No User Certificates found.

I can access the relevant sites from a client machine:
http://rmsServer/_wmcs/Certification/activation.asmx
http://rmsServer/_wmcs/Certification/Certification.asmx
http://rmsServer/_wmcs/Licensing/license.asmx

The SCP is registered
Everyone has an email address in AD
The Supers Users group is enabled for troubleshooting, but still no access
There is no problem with the RMS service account

Any help would be greatly appreciated!