Master theorem not applicable?
The three cases of the Master Theorem that you refer to are proved in the Introduction to Algorithms by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).

It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\varepsilon}$ for any $\varepsilon &gt; 0$.

However the theorem can be generalized to cover this recurrence. Consider

Case 2A:
Consider $f(n) = \Theta (n^{\log_b a }\log_b^k n)$ for some $k\geq 0$.

This case reduces to Case 2 when $k = 0$. It is intuitively clear that along each branch of the recurrence tree $f(x)$ is being added $\Theta (\log_b n)$ times. A sketch of a more formal proof can be found below. The final result is that

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$.

In the Introduction to algorithms this statement is left as an exercise.

Applying this statement to the recurrence in question we finally get

$$
    T(n) = \Theta(n \cdot \log^2 n).
$$

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

$$
   \lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}
$$

for any functions $f(x)$ and $g(x)$ differentiable in the vicinity of $c$. Applying this to $f(n) = n \log n$ and $g(n) = n^{1+\varepsilon}$ one can show that $\log n \not\in \Theta (n^{1+\varepsilon}).$



Sketch of the Proof of the Master Theorem for Case 2A.

This is a reproduction of parts of the proof from Introduction to Algorithms with the necessary modifications.

First we prove the following Lemma.

Lemma A:

Consider a function

$$
 g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)
$$

where $h(n) = n^{\log_b a} \log_b^k n.$ Then
$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Proof:
Substituting the $h(n)$ into the expression for $g(n)$ one can get
$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}}  \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

If $n$ is an exact power of $b$ given a recurrence

$$
 T(n) = a T(n/b) + f(n),\quad  T(1) = \Theta(1)
$$

one can rewrite it as

$$
 T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j f(n/b^j).
$$

Substituting $f(n)$ with $\Theta(n^{\log_b a} \log_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.