I'd try one other software (free) - before spending any money - Microsoft Acrylic
I have the August version, but it does a pretty good job of stitching and it might save you a couple of bucks. It will accept 16bit images, but seems to spit out an 8 bit pano...
Not hard, but its use isn't intuitive
File, New Vector Layer, OK
File, Insert Images (select the files you want) OK
Image, Stitch Selected Images - choose Common Vantage Point and Horizontal Cylinder - let it crunch
Object, Image, Export as Image File
at least, that's how it works in my version...
You're rotating about the nodal point (aka entrance pupil)? If not and there's close foreground, most programs will have some difficulty in dealing with the parallax.
As Das suggests, I'd be very surprised if it was the lens...