This is an NT 4 domain? SMB signing on the workstation end is the usual culprit, but that doesn't jive with it working with a Domain Admin account. Is there any sort of error message on the workstation, or a security event on the DC?

Yes, it's an NT4 domain, but you don't understand. This is not an error. There is nothing wrong at all. It's simply the lack of a feature.

If I want to add an NT4 workstation to the domain, I can do it from my desk, and I can do it at any time. If I want to add an XP workstation to the domain, I have to get up and walk to the workstation, and only at a specific moment during setup.