I managed to fix this issue following this Question:
CE1.9.1 Please make sure your password match issue during User registration
But the error still occurs when Checking out, and registering from a the Mobile.
I'll appreciate any help on the issue.