Finally had the guy bring in his computer (I was walking him through the process on the phone). Took less than a minute to solve. Turns out he had entered the wrong information into the account properties as well as in his address book. Each time I had him read back what he entered in the account properties, he was misreading the information.

Anyway.. thanks for your help on this.