What is the complexity of this problem? Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of the post was that most examples of natural questions that have been conjectured to be intermediate have subsequently been shown not to be -- the two most notable exceptions being the discrete logarithm problem (and factoring), and the graph isomorphism problem. There have been related questions here on Mathoverflow and also on TCS stackexchange. 
I asked about the status of one particular problem in a comment on the blog post but got no answer, so I'll ask it again here. The problem is the following. You're given a non-singular $n\times n$ matrix over $\mathbb{F}_2$ and asked to determine whether it can be reduced to the identity using at most m Gaussian row operations. It seems very unlikely that this problem is in P, since the problem of finding an explicit matrix that needs a superlinear number of operations is open (and, I think, thought to be hard). On the other hand, if I try to take a problem like 3-SAT and reduce it to this one, I don't have any idea where to start. But that is very weak evidence for the assertion that the problem is not NP-complete, so I'm asking again the question I asked in the blog comment: is anything known, or intelligently conjectured, about the status of this problem?
The question can be reformulated as asking for the length of the shortest path between two vertices in a certain Cayley graph. (NB, that doesn't make it polynomial-time because the number of vertices in the graph is exponential.) I'd be just as happy to be told that the same problem in a different Cayley graph was probably of intermediate complexity: I chose the Gaussian elimination example because I happen to like that graph.
 A: This is not a full answer, but perhaps too long for a comment.
Your question is about the distance problem in a fixed Cayley graph.  If one also considers the Cayley graph as part of the input then some things are known.  This makes sense in the context of permutation groups, where we can explicitly give the generators in a succinct way.
Even and Goldreich in the paper "Minimum-Length Generator Sequence Problem is NP-Hard" (J. ALGORITHMS. Vol. 2, no. 3, pp. 311-313. 1981) showed:

We examine the following questions:
  (1) Given a set of generators of a
  permutation group G and a target
  permutation P, find (the length of) a
  shortest generator sequence realizing
  P. (2) Given a set of generators of a
  permutation group G, find the minimum
  upper bound on the length of generator
  sequences needed to realize any
  permutation in G. We show that both
  problems are NP-Hard by reducing the
  3XC problem to each of them. The
  reductions we use show that these
  results hold even if the given set of
  generators is restricted to contain
  for each generator its inverse, too.

This actually makes the problem NP-Complete (when the length is written in unary).
In other work, Mark Jerrum in "The complexity of finding minimum-length generator sequences" (Theoretical Computer Science Volume 36, 1985, Pages 265-289) showed:

The computational complexity of the
  following problem is investigated:
  Given a permutation group specified as
  a set of generators, and a single
  target permutation which is a member
  of the group, what is the shortest
  expression for the target permutation
  in terms of the generators? The
  general problem is demonstrated to be
  Image -complete and, indeed,is shown
  to remain so even when the generator
  set is restricted to contain only two
  permutations. The restriction on
  generator set cardinality is the best
  possible, as the problem becomes
  soluble in polynomial time if the
  generator set contains only one
  permutation. An interesting feature of
  this problem is that it does not fall
  under the headings of ‘two person
  games’ or ‘formal languages’ which
  cover the great majority of known
  Image -complete problems. Some
  restricted versions of the problem, in
  which the generator set is fixed
  rather than being part of the problem
  instance, are also investigated and
  shown to be computationally tractable.
  One result of this kind is that
  determining the most compact
  expression of a permutation in terms
  of ‘cyclicly adjacent transpositions’
  can be achieved in polynomial time.
  Thus, from an initial arrangement of
  distinct objects on a circle, one can
  quickly compute the smallest number of
  interchanges of adjacent objects
  required to realise any other
  arrangement. Surprisingly, this
  problem appears substantially more
  difficult to solve than the related
  one (for which a solution has been
  known for some time) in which the
  objects are arranged on a line
  segment.

Note that Jerrum considers the length of the path in binary, which changes things.
A: If one relaxes the question to asking the row-reduction distance of arbitrary matrices over $\mathbb{F}_2$ then it can be shown that the problem is $NP$-Complete.  That is, consider

RRD (Row Reduction Distance):
Input: $m\times n$ matrices $M$, $N$
  over $\mathbb{F}_2$, and an integer
  $k$ 
Output: Whether $M$ can be row-reduces
  to $N$ in $\le k$ steps

The claim is that this problem RRD is $NP$-complete.  It is within $NP$, so the hardness is all that remains.  To do this, consider the following related problem.

MHW (Min Hamming Weight): 
Input: $P\in\mathbb{F}_2^{m\times
> n}$, $b\in\mathbb{F}_2^n$, integer $k$
Output: Is $b$ expressible as a linear
  combination of $\le k$ rows of $P$.

I'll first show that MHW reduces to RRD, then show that RRD is $NP$-hard.  This together will show RRD is NP-hard.
Let $(P,b,k)$ be an instance of MHW.  Create $M$ and $N$ as $(m+1)\times n$ matrices, where $M$ is just $P$ with the zero row appended on, and $N$ is just $P$ with the row $b$ appended on.  I'll now show that $b$ is expressible as a linear combination of at most $k$ rows of $P$ iff $M$ is row-reducible to $N$ it at most $k$ steps.
The forward direction of this claim is straightforward.  Now for the backward direction.  Row-reduction operations over $\mathbb{F}_2$ are just "add this row to that row", or "swap this and that row".  It follows that in $\le k$ row-reductions have at most $k$ "source" rows of where the additions come from.  Thus, the last row of $N$ is equal to the last row of of $M$ (which is zero) plus at most $k$ other rows of $M$.  This is exactly what was wanted, as the last row of $M$ is just $b$.
This completes the proof that MHW reduces to RRD.
Now let's show that MHW is NP-hard.  We'll do so with:

SET-COVER
Input: Sets $S_1,\ldots,S_m\subseteq[n]$, integer
  $k$,
Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets $S_i$

It is know that Set-Cover is NP-complete.  Here we need a slightly stronger version of this fact, where all of the sets are of constant size, and this is still NP-complete. (To see this, one first shows that 3SAT is still NP-complete when each variable appears in at most 3 clauses.  Then one runs through the "standard" reduction from 3SAT to Set-Cover, and notices that all of the sets are of constant size).
Now consider a set-cover instance.  Note that if we through in all subsets of each $S_i$, the answer to the cover question doesn't change.  Note that we can do this as each subset is of constant size, so there aren't too many subsets to add.  Thus we get

Hered-Set-Cover
Input: Let $\mathcal{S}\subseteq
> 2^{[n]}$ be a family of sets, each of
  size $O(1)$, that is subset closed. 
  Let $k$ be an integer.
Ouptut: Decide if $[n]$ is the union
  of $\le k$ of the sets from
  $\mathcal{S}$.

and Hered-Set-Cover is NP-complete, as argued above.  We'll now reduce Hered-Set-Cover to MHW.  Take a Hered-Set-Cover instance, with the family of sets $\mathcal{S}$ and integer $k$.  Suppose there are $m$ sets.  Then write out $P$ to be the $m\times n$ matrx where the rows are the indicator vectors for the sets in $\mathcal{S}$.  The target vector $b$ is the all ones vector, and $k$ is as in the original problem.  So if $b$ is a $\le k$ linear combination of the rows, then this immediately gives the set-cover of $\le k$ sets.  If there is a set-cover of $\le k$ sets, then we can always pass to subsets so that each element in the ground set is covered exactly once, and thus when we sum up the relevant vectors in $\mathcal{F}_2$ we never run into the issue that 2=0.
So really we are doing a "set-cover with odd covering at each vertex" in the MHW instance.  The point is that allowing the subsets in the family makes the exact number of coverings irrelevant, and so we can assume things are covered exactly once.
It seems like there might be a more direct reduction from the problem Exact-Cover (where in set-cover we require that each element be covered exactly once).  Indeed, I sort of just untangled the reductions needed to use Exact-Cover.  But Exact-Cover doesn't seem exactly right, because if $b$ is a $\le k$ linear combination this doesn't immediately translate to an exact cover.
This approach doesn't seem to address the issue when $M$ and $N$ are full-rank in the RRD problem, as the reduction of MHW to RRD needs non-full-rank, and the MHW problem is solvable in polynomial time when $P$ is full rank.
