If I'm following correctly. Everything is done so far that you have noted here but the new user is failing to authenticate at preboot. Is that correct?
Any user that is new to MDE will be in a default state. I'm not sure if that user has attempted using the default password to start with but that would be one item to test with but we have to keep in mind that depending upon your policy configuration too many incorrect attempts could lock the user out from any further attempts.
If the user account is not in the new/default state, another option would be to complete a token reset for the user either through challenge/response or if you are able to get back in to the OS, through the DE: Users query which will then need to by updated on the client system before rebooting.