Problems with big open complexity gaps
The Knot Equivalence Problem. 

Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity obstructions to its being in P. The best upper bound currently known on its time complexity seems to be a tower of $2$s of height $c^n$, where $c = 10^{10^{6}}$, and $n$ is the number of crossings in the knot diagrams. This comes from a bound by Coward and Lackenby on the number of Reidemeister moves needed to take one knot to an equivalent one. See Lackenby's more recent paper for some more recent related results and for 
the explicit form of the bound I give above (page 16).