In this job market, you'll need lots of experience and a degree to get hired at a major. It's supply and demand for sure, and right now the demand is low and supply is deep.
Still, sometimes you can't make heads or tails of airline hiring. The year I got hired (and I maintain I was the LCD), I heard stories of guys with space shuttle missions, along with other high profile positions being rejected at my company. Truth is, there isn't any such thing as a sure thing.
I'd rather be lucky than good any day.
To the original poster, which airline told a guy why they weren't hired? That story is a little suspicious.