When I was out there, it was blocking Computer-to-Phone, but Computer-to-Computer was okay.
I got around it by switching to a different serveice to Skype for Computer-to-Phone (sorry, but I don't have the name of that one on this machine and, if it gets popular then Etiselat and the other phone company will probably block that one too), but note the comments above which may solve the problem.
It's not all the ME that are blocking it - as far as I know only UAE (no problem in Qatar, BAH or KSA).
Good luck!