I don't find this unbelievable or even shocking because I've heard of these:
http://en.wikipedia.org/wiki/Diploma_mill
I'd find it shocking if someone I trusted used a fake reference service or a diploma mill, but it's not at all shocking that these exist.