Thanks for the advice.  I've checked it out, but it all seems like stuff I have already tried.

I am seeing this error in the SQLAgent Error log:

[241] Startup error: Unable to initialize error reporting system (reason: Access is denied)

From what I understand, the error reporting system is what Microsoft use (new feature in SQL Server 2000 SP3) to automatically report errors with SQL Server running to Microsoft (same way Windows pops up a dialogue box asking 'do you want to send this error to Microsoft' when something messes up in Windows).  This however is an option to install at the time of SQL being installed, and we have not chosen to install it.  I can confirm this by opening the SQL Server properties and seeing that the 'Enable the Error Reporting Feature' is unchecked/disabled.

It sounds as if the Error reporting is still being initialized when the SQLAgent is started, and hence, permissions related to this.

Does anyone know more about the Error Reporting Feature, or more information about the error I have been seeing?