Hi Marc,
Doing a "desc google.search' query shows that the table takes in an "apiKey". Can you try providing your own API key in your query. I suspect that there is a single default in use for demo purposes and that is being blocked by Google.
You can confirm by selecting the "Debug" option when running your query on the YQL console, and then clicking on the UUID hyperlink that shows up next to googleapis.com url in the response, like below:
<url execution-start-time="419" execution-stop-time="989"
execution-time="570"
id="dc1d524b-13da-4246-8fff-083a71f91af2" proxy="DEFAULT"><![CDATA[http://ajax.googleapis.com/ajax/services/search/web?v=1.0&gl=en&userip=&hl=en&q=pizza&start=0&rsz=8]]></url>Sriram