The rub is here: "slide the curve off the cut locus". The problem: the cut locus might be a humongous growth whose diameter is large compared to that of $M$. The diameter of $M$ can be kept small by embedding the growth in $M$ in a way that attaches it to a small base.
This concept is closely related to the filling length of a loop, which Gromov defined to be the infimal $L$ such that the loop can be contracted to a point via loops of length no longer than $L$. You can visualize the two definitions as asking for a homotopy where the leaves of a certain foliation are bounded by some estimate. In the definition above, these are radii; in the other defition they are concentric circles. By reparametrizing, one can be converted to the other with only bounded loss of efficiency.
In The Morse Landscape of a Riemannian Disk by Frankel and Katz, they prove that Riemannian metrics on a disk of bounded length can have arbitrarily large filling length, that is (my rephrasing):
(Theorem 2) for every constant $C$ there is a $g$ on the disk $D^2$, of boundary length $1$ with every point of $D$ is within distance $1$ of the boundary such that every homotopy of $S^1$ to a point in $(D,g)$ contains an intermediate curve of length bigger than $C$.
Tim Riley and I developed a related construction in The absence of efficient dual pairs of spanning trees in planar graphs where we constructed cell complexes of bounded geometry (the complex and dual both have valence $\le 6$) where the filling length is a quadratic function of diameter. We also showed that quadratic behavInior is sharp. We used this to show that for all spanning trees in the complex, the length of the tree plus the length of the dual tree is bounded below by a quadratic function of the diameter of the graph.
You can interpret this as saying that there is no way to sweep across the disk with arcs whose maximum length is less than a quadratic function of the diameter of the disk.
These examples also show that for homotopies of the boundary to a point, some point must travel an unbounded distance for arbitrary diameter 1 metrics on the disk, and a quadratic function of diameter, if there are curvature bounds. These examples work for all higher dimensions.
In both constructions, the cut locus is has a large diameter, considerably larger than the diameter of the metric itself. To construct the metrics, start with a tree that branches 3 ways at each vertex, and thicken it by replacing the vertices triangles at the vertices and rectangles for edges. Now glue on a strip, all the way around, cut out of the hyperbolic plane between two concentric horocycles with the long edge along the tree and the short edge on the outside. This achieves the metric of bounded diameter. Here are the relevant figures from our paper. The idea is that the lines of any homotopy end up having to cut across the tree numerous times, each time losing some efficiency. See the two cited papers for details.
alt text http://dl.dropbox.com/u/5390048/Tree%20pictures.jpg
Added: See the answers of Sergei Ivanov and Ian Agol for nice and more general methods that work in higher dimensions.