No BB connection while roaming

[kuduIT]

I have two users traveling in different areas (one in Oman and another in Kazakhstan) who cannot connect to BB data. Both devices can make calls, browse to the internet, and use text messaging. Neither are connecting to BB services (the four dot icon is not on the screen). I have tried battery pulls, SIM card pulls, upgraded to the latest OS, re-registered the Hosting Routing Table, resent the service books OTA, and by connecting the phone to a laptop with Web Desktop, I have called out local provider and they say it's RIM. RIM says it the provider. Both phones connected to Vodaphone NL (visible in the BES) while on a layover to their final destinations. I don't know if there is a specific issue with the in country carriers, and I am hoping someone else here might have dealt with this issue. The Kazakhstan carrier is KCELL and I don't have the Oman carrier. Anyone had an issue like this before?