Technofreak:freitasm: IIRC Windows Phone 8 had problems with non-alphanumeric characters in password fields with Yahoo! Mail.
Hmmm, No non alpha numeric characters being used, so that's not likely to be the problem. Though each time the set up fails it asks for a new password.
Have you taken the device in to a Telecom store? They may be able to provide you with a fix in store.