Are the sharepoint services logging in with a domain account? Basically are you sure sharepoint is trying to connect using the credentials you think it is? Was the sharepoint computer in another domain when sharepoint was installed?

I'm grasping here for anything, because I agree, its weird.

CEWII