Which version of Photoshop are you using? CS2 vs. CS3 is a huge difference.
Photomerge (CS3) works by identifying "features" in each of the images, and then matching up. The algorithm is called SIFT (Scale Invarient Feature Transform). For details, see:
http://en.wikipedia.org/wiki/Scale-invariant_feature_transform
It's hard to tell without seeing the images in question, but it could be the higher magnification images don't produce the kind of locally distinct features the algorithm needs to get traction on. Increasing the overlap and/or the contrast (e.g., via histogram equalization or similar techniques) may help.