Personally, I find it very believable that a college football player, who comes from a conservative, Mormon family, was duped by an acquaintence playing an (elaborate) practical joke on him.
I could see Te'o really believing that his girlfriend was real...but lying about the fact that he had met her. It could have been to him an online romance, that was cut short of him getting to consumate it by meeting her, when she tragically died.
And he made up the story of how they met and become friends, and how he sees her when they are both in Hawaii, and all that, to hide the embarrasing fact that he not only met her online, but had not actually met her in person. Particularly with his Mormon upbringing, since they would have likely not been thrilled about him having an online romance.
There are a lot of gullible people out there, and when you are talking about 22 year old college football players (or however old he is), then the percentage of gullibility probably rises a decent amount.