Yep, what Sam said, except for the part about requesting a refund. ;) PTGui can do some great stuff, but it isn't exactly bulletproof either (it will also choke if you have too much overlap in your images).
BTW, the reason we are suggesting less overlap to your images is because all image-stitchers like to have orderly input data, and then match some detail in image A - B, then B - C, etc. When there is the possibility to match a detail that is in A - B, and A - C, as well as B - C, the stitching process doesn't do a better job, it just has more work to do matching features!
Also, Stitcher reads the EXIF of your input images to determine lens focal length, but it also considers how many images you have loaded (in case you cropped the images, as Sam suggested). So, it might see your input images as 15mm equivalent, but then see so many images and think "oh, that many images is closer to what I'd expect for 20mm" (no, it doesn't actually think that...).
So it all sounds rather "black box" but in truth, any panoramic stitcher is going through the same calculations and assumptions to set up the stitching process, unless it asks you for manual input of everything. That's the "automatic" part that many people are quite reliant on today, which further adds to the confusion when it doesn't just work.