Ok, this is definatly a computer issue, not a user account issue. Setup that same user on another box, no issue.
Next step is to rebuild his windows profile on his current box to see if it can save pw's after a reboot. If so, I still need to track down what has change/become corrupt. Rebuilding profiles on all these machines is not an option, especially if it can just happen again.