When I had to restore from Time Machine following the failure and replacement of my iMac's hard drive, I experienced no problems.
From what I can see here, is it possible that when restoring from TM one requires the password in use at that time (such that earlier and later passwords would not work)?