It turned out Orange was to blame after several frustrating phone calls. They had billed me for it but did not have the provisioning setup. I was doubting my BES setup on Exchange and removed it / set it up again. Wiped the phone on multiple occasions. All for nothing, but at least it was a lesson learned. Thanks for everyones help.