In this talk I describe ongoing work on my attempts to improve this lower bound. Instead of considering the minimum spanning tree itself, I consider the quantity
Geometrically, the shape formed by plotting q(x) against x is a lower envelope (min) of an upper envelope (max) of certain sets of lines (plots of each individual edge weight). The upper envelope of lines is a concave chain, so q(x) is the lower envelope of certain concave chains. It forms a monotone path in the line arrangement (monotone simply means that it is the plot of a function, having only one intersection with any vertical line). The convex vertices in this path correspond to minimum spanning tree changes, although the concave vertices may not.
My first attempt to prove a better lower bound on the number of minimum spanning trees starts from a construction of Matousek, who showed that monotone paths in arrangements may have complexity Omega(m5/3) (no nontrivial upper bound is known). Since Matousek's lower bound on monotone paths is larger than our known upper bound on minimum spanning trees, there are some monotone paths that do not correspond to minimum spanning tree sequences. I tried a simplified example in which m lines are partitioned into sqrt m "cables" of sqrt m lines each, with an additional m lines connecting up the intersections of pairs of cables in such a way that each intersection contributes sqrt m vertices (both convex and concave) to the monotone path. It is possible to represent this monotone path as a lower envelope of a simple family of concave chains, however when I tried to translate this family back into graph-theoretic terms I ended up with "coat-hangers" (triangles with a dangling edge) instead of paths.
Instead, I tried restricting the problem further, to paths in series-parallel graphs. Series composition corresponds to forming q(x) as the upper envelope of two paths coming from the two subgraphs being composed, and parallel composition corresponds to a lower envelope. Therefore, one can re-interpret the problem as a form of "constructive solid geometry" for monotone paths: one is given a set of monotone paths, initially just m lines, and can repeatedly perform operations that combine two paths, replacing the two by a single upper or lower envelope. How complex a path can result from this process? The bounds I currently know are exactly those for the original parametric MST problem, Omega(m alpha(n)) and O(m sqrt n).
In summary, I still haven't made progress in narrowing the gap between lower and upper bounds for parametric MSTs, but at least I've found some interesting ways of translating the problem into some geometric formulations that don't look like they should have anything to do with MSTs.