The UAE actively blocks VOIP calls. I believe it does more than just port-blocking, and uses deep packet inspection to identify and block VOIP calls.
You could try using a provider that allows you to connect on Port 80 (rather than 5060) or use your existing provider but route it through a virtual pbx like
www.pbxes.org which does allow connections on Port 80.
Saying that, it may still not work, the UAE blocking is quite heavy.