Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?
One natural example is finding the longest increasing subsequence of a sequence of $n$ numbers. Candidate subsequences can be linked in the input sequence. This is a fairly common exercise, and works for other type of subsequences, too. It is actually the exercise 15.4-6 in the 3rd edition of the Cormen et al. book too. For an algorithm, see Section 2.2 in these notes.
To expand on my comment:
While sorting is not doing a "table lookup", remember the actual definition of DP:
Method for solving problems that have optimal substructure.
We see that a divide-and-conquer approach for sorting satisfies this.