I have some problems with the blackberry units over in our London branch.
They had e-mails going through the blackberry e-mail service and NOT through BES. Anyway, they had to have their MX records updated.
Previously, they had mail collected at their ISP and then downloaded using a POP connector, e-mails went through fine to their blackberry. I updated the MX record to go directly to their server so that they weren't missing out on e-mails and exchange caught them all automatically.
I am assuming that the reason it isn't working now is because the MX records and credentials have changed. They said that they have reset the blackberrys and tried setting up from scratch. Still no luck.
They are using the Blackberry Pearls on the O2 network.