Eureka, found the solution for me, hope it works for others...
1. You need to get your BES admin to delete the configuration of phone type (e.g. 8100, 8310, 8310) and change it to NONE.
2. Uninstall GoogleMaps
3. Reset your device
4. Install GoogleMaps.
5. Change the permissions in google maps to allow.
Bingo, you should be in business!
Hope that helps others like me!