The PIN is provisioned for both BIS and BES. What does the user have for signal strenght? If they check Options>Status on their device, it should less than -95dBm but higher than -40dBm.
Try again to remove/readd the BB, create your own EA password, 'a' works best

Eliminate as much user error as possible.
Watch the EA and see where it fails. The check the MAGT log for the users email address around the time it failed. The log should state why it failed.