Vista - Unable to create user profile

Vista Business, on an AD domain
For a specific user I am getting the message when logging on first time:
"Your user profile was not loaded correctly! You have been logged on witha
temporary profile. Changes you make to this profile will be lost when you log
off..."
This user logs on properly on another Vista machine; I can create other
domain users on the samemachine.
The user is created using an administrative account and with administrative
privileges.
The user was previously created and logged in to that machine in a
double-profile (one local and one domain). I have deleted both profiles and
recreated the user's profile to be domain only when the problems began. This
is probably a hint, but I have no idea what to do with it.
The Event Viewer yields nothing.
Short of reinstalling Vista, is there something I can do?

Thanks,
Ofra