Consider the recent restriction by Saudi Arabia on Qatar Airways flights, which prevents Qatar flights from flying over Saudi airspace. Qatar now has to use longer routes and go fly around the land mass. Does the ICAO not prevent Saudi Arabia from this kind of behavior?
Yes they can.
There was an attempt to allow one to pass over a country freely with the Freedoms of the Air however this is not a blanket thing and not everyone partakes.
....As of the summer of 2007, 129 countries were parties to this treaty, including such large ones as the United States of America, India, and Australia. However, Brazil, Russia, Indonesia, and China never joined, and Canada left the treaty in 1988. These large and strategically located non-IASTA-member states prefer to maintain tighter control over foreign airlines' overflight of their airspace, and negotiate transit agreements with other countries on a case-by-case basis.:23 Since the end of the Cold War, first freedom rights are almost completely universal.:151 Most countries require prior notification before an overflight, and may charge substantial fees for the privilege (see the wiki article for references)
Does the ICAO not prevent Saudi Arabia from this kind of behavior?
In principle yes, by article 9 of ICAO Chicago Convention on International Civil Aviation.
Each contracting State reserves also the right, in exceptional circumstances or during a period of emergency, or in the interest of public safety, and with immediate effect, temporarily to restrict or prohibit flying over the whole or any part of its territory, on condition that such restriction or prohibition shall be applicable without distinction of nationality to aircraft of all other States.
This would apply to any ICAO member State, which includes Saudi Arabia.