You need to do a password reset for the user, a machine recovery does not affect the individual user profiles.
Of course, should have tried that. I am new with EEPC and the fact that he got the error without ever having logged in to the pre-boot on the new machine made me conclude that something had gone wrong with the sync (and that the default choice of Machine Recovery in EPO was made based on the challenge code).
After doing a User Recovery/Reset Token everything works fine. Thank you very much for your help.