Googlebot can't access your site
Over the last 24 hours, Googlebot encountered XX errors while attempting to connect to your site. Your site's overall connection failure rate is XX%. You can see more details about these errors in Webmaster Tools.
After you think you've fixed the problem, use "Fetch as Google" to verify that Googlebot can properly access your site.
The site was loading fine from all possible locations so I tried this "Fetch as Google" thing. Which resulted in an endless "pending" status that finally turned into "Failed":
I spent hours trying to investigate and finally found a solution. So if you ever bump into this, here goes
It was the old Google Analytics tracking code. Somehow it blocked Googlebot from indexing your website in some cases.
Just upgrade to the new, asynchronous tracking code and use the "Fetch as Google" tool once again.