First thing I can offer is to get back on to the carrier and tell them they are wrong and the SIM isn't correctly provisioned for BES. Ok so maybe it is but usually this is the fault so I would always err on the side of blaming them until they have confirmed it on a couple of separate occasions. Virtually every post like this is down to the provisioning and the carrier just has to be hounded till they admit they messed up (or don't but fix it anyway!).
I was a BES and Exchange admin once.
Then my world turned Blue.