Problems Between P and NPC Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete.  What are some other (sufficiently different) natural problems that share this property?  Artificial examples coming directly from the proof of Ladner's theorem do not count.

Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?
Here's a collection of some of the responses of problems between P and NPC:

Factoring
Isomorphism problems: Graph Isomorphism [not NPC unless $\sum_2^p=\prod_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, Ring Isomorphism and Automorphism (via @Joshua Grochow)
Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
The Turnpike Problem of reconstructing points on line from distances (via @Suresh Venkat)
Problems arising from the Unique Games Conjecture (via @Moritz)
Discrete Log Problem and others related to cryptographic assumptions (via @Joe Fitzsimons)
Determining winner in parity games (via @mashca)
Determining who has the highest chance of winning a stochastic game (via @Peter Shor on MO)
Numbers in boxes problems (via @Joshua Grochow)
Agenda control for balanced single-elimination tournaments (via @virgi)
Knot triviality (via @JeffE)
(Assuming NEXP≠EXP) padded versions of NEXP-complete problems (via @Joshua Grochow)
Problems in TFNP (via @Marcos Villagra)
Intersecting Monotone SAT (via @András Salamon)
Minimum Circuit Size Problem (via @Eric Allender)
Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
The Cutting Stock Problem with a constant number of object lengths (via @Suresh Venkat)
Monotone Self-Duality (via @Danu)
Planar Minimum Bisection (via @turkistany)
Pigeonhole Subset Sum (via @user834)
Square Root Sums (via @JeffE)
Deciding Whether a Graph Admits a Graceful Labeling (via @Oleksandr Bondarenko)
Gap version of the closest vector in lattice problem GapCVP$(\sqrt{n})$ (via @MCH)
The linear divisibility problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
Finding the VC dimension (via @Mohammad al Turkistany)
Finding the minimum dominating set in a tournament (via @Mohammad al Turkistany)