The fps should not matter. The tracker only looks at the single frames, no matter what the fps is.
About the huge difference: The fact that blender was actually able to solve the one shot correctly is actually really surprising and was pure luck. Yes, you can get great tracking results with only 8 markers, but these markers should ideally cover the entire frame, and, most importantly, they must not be just a flat plane, but at the very least one or tow should introduce some depth.
That’s not just a requirement of Blender but of all trackers. See this tutorial about Syntheyes, which describes a similar problem: https://www.youtube.com/watch?v=QmL-UbwfUtY&feature=youtu.be
If you are a cloud member you can check out Track Match Blend 2, which should cover everything you need to know: https://cloud.blender.org/p/track-match-2/