Check the security rights on the BES account added in the AD and Mailbox security properties of the User's account. I had the same issue on one blackberry and I almost gave up. I tried everything to no avail. Modified the rights to grant more security rights and presto. Everything starts to work properly.