Super-linear time complexity lower bounds for any natural problem in NP?

Sorry I am so late to the discussion, but I just registered...

There are non-linear time lower bounds on multitape Turing machines for NP-complete problems. These lower bounds follow from the fact that the class of problems solvable in nondeterministic linear time is not equal to the class of those solvable in (deterministic) linear time, in the multitape Turing machine setting. This is proved in:

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

In fact, unraveling the proof shows that there must be some problem solvable in nondeterministic linear time that is not solvable in $o(n \cdot (\log^* n)^{1/4})$ time (again, on a multitape Turing machine). Note the * in the logarithm; this is just "barely" above linear. One known application of this result is that a natural NP-complete problem in automata theory cannot be solved in $o(n \cdot (\log^* n)^{1/4})$ time:

Etienne Grandjean: A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19(3): 438-451 (1990)

Unfortunately the lower bound of Paul et al. relies crucially on the geometry that arises from accessing one-dimensional tapes. We don't know how to prove a non-linear lower bound even if you allow the Turing machine to have a constant number of two-dimensional tapes. We can prove time lower bounds for NP problems on general computational models if you severely restrict the extra workspace used by the machine. (This is getting into my own work so I won't say more unless you're truly interested.)

As for the comment above me: the sorting lower bound holds only in a comparison-based model, which is extremely restricted. The claim that sorting requires Omega(n log n) time on general computational models is false. There are faster algorithms for sorting integers. See for example:

Yijie Han: Deterministic sorting in O(n log logn) time and linear space. J. Algorithms 50(1): 96-105 (2004)

For the circuit model, the answer is NO. The best general lower bounds are linear.

(As Ryan explained in his answer and comment for multi tape Turing machines there are (slightly) superlinear bounds. As far as I understand from his comment for random access Turing machines there are no superlinear lower bounds known.)

If you restrict space usage to be sublinear then you can prove superlinear time lower bounds on SAT. See this article on Lipton's blog for a nice exposition.