I meant to include a link to the KB, just realised I forgot so sorry about that.
Glad you have it sorted.
As you are in a similar configuration to us, do you know if you have any issues with passwords that are 15 characters or longer? Or if you use a Colon in the password, does this also fail?
BES 5.0.3 MR4
Exchange 2010 (SP1 RU3)
SQL 2008 R2