Automatic Update service failed to start - Event ID: 7023

I had this same issue on a laptop a couple weeks back, which
seemingly appeared out of nowhere. I never was able to get
the issue resolved, as every solution I found seemed to
pertain to WSUS, which we do not use.

I just received a new HP desktop in yesterday. It already has
Windows XP SP3 installed and aside from installing Office 2007,
and adding the PC to the domain, I have done nothing.

When I try to run Automatic Updates via the webpage, I get an
error stating either the AU, Event Viewer or BITS service is
not started. BITS and Event Viewer are fine, but when I try
to manually start the AU service, I receive the following error.

"Could not start the Automatic Updates service on the Local
Computer. Error 0x80004015: The class is configured to run as
a security id different from the caller."

When I check the event logs, I see the following entry.
"The Automatic Updates service terminated with the following
error:  The class is configured to run as a security id different
from the caller. Event ID 7023"

I removed the PC from the domain and the AU service worked
just fine. I rejoined the PC to the domain and had the same
problem. I am logging into the PC as the local admin and have
tried logging in as myself (domain admin), so I don't suspect
a rights issue.

We have not modified out group policy in any way and are not
using a WSUS server. As of right now, only these two users
are experiencing these issues and there seems to be no
differentiating factor.

Any ideas?