markturner, by any chance the error message your are getting say this instead?
"Cannot
log on to Exchange Server. Please check server access or provide a valid password"
Which is slightly different than the error from your op. If so, see this >>
Cannot log on to exchange server - BlackBerry Support Community Forums