That is because the US DoD – who 'own' and manage GPS – intentionally degrades the GPS data it provides Google (a.o.) for certain parts of the world, of which the Middle East is one. Their reasoning: "Suicide bombers are already too accurate. We are not going to help them with super accurate GPS".
I.o.w. navigation using GPS will not work in the Middle East (or in any region) as long as the US don't want it to. As they demonstrate...
That (typical) attitude – and the fact that GPS satellites will start dropping out of the sky in 2 years time (and the US can't afford a replacement system; they're broke) – is reason for the EU, Russia, and China to develop their own satnav systems Galileo, Glonass, and Baidu. The first satellites have already been launched. The systems are planned to go online in about 2 to 3 years time.
And Japan, India, Brasil, and Australia are all also seriously considering to develop their own satnav systems.
Of course there is only one smartphone, the just announced
Samsung Note, not yet even available in stores, that can handle another sat/nav system than GPS. Namely the Russian Glonass.
Other smartphones will most probably follow suit, but we'll have to wait and see.