Photoshop CS5 has many (maybe too many) options for stitching photos together. Have you tried all of them? I can just about always find an option that works for me no matter what the subject. I use MS -ICE sometimes, but I have mostly been very disappointed in its abilities. The stitch program which came on my camera software CD does a better job than ICE.
No I don't have CS5 yet. Maybe it's time I picked it up
I could tell you but I wouldn't want you to get all pissy if it's the wrong brand