This isn't really an answer, but why don't you try a different stitching program? Autopano Pro and PTGui are often recommended: I've only used the former, which I find pretty good (better, in my hands anyway, and easier to use than PS). It will at least give you some indication if your frames are stitchable (automatically) at all.
Jeremy