Thanks guys, the problem has been resolved. We made two changes prior to the last server reboot:

1.Changed the service timeout from 30000 to 120000 (http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2776350&SiteID=1)

2.We found a DCOM security issue on the server, so we granted Local Activation permission to the Network Connection Manager Class {BA126AD1-2166-11D1-B1D0-00805FC1270E} to the user NT AUTHORITY\NETWORK SERVICE, as suggested in the event log

Not too sure which step actually fixed it - or if another reboot was all that was required?

Thanks again!