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