One of the other changes made was to start up the Search Service - previously we had the Office and SharePoint search services disabled, as they were causing errors with the old SQL Server - long story about that! In doing so, I had to update the SSP config page to start up the services.
Looking in the event log, there were a ton of errors complaining "unable to start service process. SSP:
I stopped & started both the Timer and Queue services, but that didn't help. Tried restarting both a few times. Tried an IISReset. Still didn't help.
My service account was set up to Log On As Service in the Local Security Settings User Rights Assignments, Log On as a service, so that wasn't it either.
What did the trick was to change the account used for both services in the Services control panel. The services were set to use the Farm account - I switched this back to using the SSP account instead, restarted the services, and we're up & running with nice quiet logs.