I've recorded this scene in 1080p60fps, and I cannot for the life of me get a solve error of below 2. I've got the focal length set to auto, so I'm not sure what's going on. I've done motion tracking in Blender before and it worked out well, but I seem to be getting a bad track.
I was pretty easily getting a solve error of 0.81, so there's nothing wrong with your footage:
So I bet you don't use your tracking properly. I just use a defined range of frames for the Solve as you can see in my screenshot which has lots of camera perspective shift. Then I used the "Detect Features" function to let Blender automatically track some points and I only erased those with erratic spikes in the Graph editor view. I added a few more markers manually to align the floor and origin as well as the axises. After I let Blender redefine Focal Length and K1 once I already got a pretty decently low Error. In the end it adjusted the Focal length to 32.6210899.
Just follow the great Track, Match, Blend! tutorial to understand the common way of how to achieve a good result.