There are some real subtleties involved here.
GitHub have clearly benefited from the network effects of being the de-facto platform for open source. Their free tier doesn't include any private repos, so it won't cannibalise sales of paid tiers. I think that their free tier is effectively a trial on steroids - you're free to contribute to open source projects, engage with the user community and learn the platform, but you have to start paying from day one if you intend to use GitHub for commercial projects.
Heroku's free tier is again a sort of supercharged free trial, in that the free tier is too limited to use in production. The free tier offers very little value to users who have no intention of ever upgrading to a paid tier.
AWS's free tier is just a very generous free trial - after twelve months, you have to start paying.
I think in all cases, the key factor is whether there's a concrete plan for how the free tier feeds into your business. If your product has high switching costs and requires a big investment in learning to use effectively, then it may make sense to have a free tier specifically aimed at letting people learn the platform. Network effects are the obvious case where free users have real business value. I think that the mistake comes from the presumption that there ought to be a free tier, regardless of whether there's a compelling business case for it.
As regards you contention that almost every big SAAS product offers a free tier, I think there are at least as many counterexamples - Salesforce, SAP, Citrix, Blackboard, Basecamp, Moz, Kissmetrics.