Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$ On pages 95 and 96 of the third edition of the CLRS book, we find
the following, which applies here since $a=b$ is all
it takes to block the application of the Master Theorem: "Although
$n\lg n$ is asymptotically larger than n, it is not polynomially
larger because the ratio $\tfrac{n\lg n}{n}=\lg n$ is asymptotically
less than $n^{\epsilon}$ for any positive constant $\epsilon$. Consequently,
the recurrence falls into the gap between case 2 and case 3." For a solution, the authors send us to exercise 4.6.2 on page 106:
"Show that if $f\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k}n\right)$,
where $k\geq0$, then the master recurrence has solution $T\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k+1}n\right)$.
For simplicity, confine your analysis to exact powers of b."
(Here $\lg^k n$ is CLRS's notation for $(\log_2 n)^k$.)
This is where I am starting to have problems...
 A: Since  this question  is asked  frequently I  will try  to work  out a
solution for generic positive integers $a$ where $a\ge 2$.
Suppose  we have  $T(0)=0$  and 
$$T(1)=T(2)=\ldots  =T(a-1)=1$$
and  for $n\ge  a$ 
$$T(n) = a T(\lfloor  n/a \rfloor) + n \lfloor \log_a  n \rfloor.$$
Furthermore let the base $a$ representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_a n \rfloor} d_k a^k.$$
Then  we can  unroll the  recurrence to  obtain the  following exact
formula for $n\ge a$
$$T(n) = a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
a^j \times (\lfloor \log_a n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_a n \rfloor} d_k a^{k-j}.$$
Now to  get an upper bound  consider a string consisting  of the digit
$a-1$ to obtain
$$T(n) \le a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
a^j \times (\lfloor \log_a n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_a n \rfloor} (a-1) \times a^{k-j}.$$
This simplifies to
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
a^j \times (\lfloor \log_a n \rfloor - j) \times (a-1)
\sum_{k=0}^{\lfloor \log_a n \rfloor-j} a^k$$
which is
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
a^j \times (\lfloor \log_a n \rfloor - j)
(a^{\lfloor \log_a n \rfloor + 1 -j} -1)$$
which turns into
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
(\lfloor \log_a n \rfloor - j)
(a^{\lfloor \log_a n \rfloor + 1} - a^j).$$
The sum produces four terms.
The first is
$$\lfloor \log_a n \rfloor^2 
a^{\lfloor \log_a n \rfloor + 1}.$$
The second is
$$- \lfloor \log_a n \rfloor
\frac{a^{\lfloor \log_a n \rfloor}-1}{a-1}.$$
The third is
$$- \frac{1}{2} a^{\lfloor \log_a n \rfloor + 1}
(\lfloor \log_a n \rfloor -1) \lfloor \log_a n \rfloor$$
and the fourth is
$$\frac{1}{(a-1)^2}
\left(a + a^{\lfloor \log_a n \rfloor} 
(\lfloor \log_a n \rfloor (a-1) -a)\right).$$
This bound  represented by these four  terms plus the  leading term is
actually attained and cannot be  improved upon. For the asymptotics we
only need the dominant term, which is
$$\left(a - \frac{1}{2} a \right) 
\lfloor \log_a n \rfloor^2 
a^{\lfloor \log_a n \rfloor}
= \frac{1}{2} a \lfloor \log_a n \rfloor^2 
a^{\lfloor \log_a n \rfloor}.$$
Now for  the lower bound,  which occurs with  a one digit  followed by
zeroes to give
$$T(n) \ge a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
a^j \times (\lfloor \log_a n \rfloor - j) \times 
a^{\lfloor \log_a n \rfloor-j}.$$
This simplifies to
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
(\lfloor \log_a n \rfloor - j) \times 
a^{\lfloor \log_a n \rfloor}$$
which is
$$a^{\lfloor \log_a n \rfloor}
+ a^{\lfloor \log_a n \rfloor}
\sum_{j=0}^{\lfloor \log_a n \rfloor -1} 
(\lfloor \log_a n \rfloor - j)$$
which finally produces
$$a^{\lfloor \log_a n \rfloor}
+ a^{\lfloor \log_a n \rfloor}
\sum_{j=1}^{\lfloor \log_a n \rfloor} j$$
or
$$a^{\lfloor \log_a n \rfloor}
+ \frac{1}{2}
\lfloor \log_a n \rfloor (\lfloor \log_a n \rfloor +1)
a^{\lfloor \log_a n \rfloor}.$$
The dominant term here is
$$\frac{1}{2}
\lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$
Joining the dominant terms of the  upper and the lower bound we obtain
the asymptotics
$$\color{#00A}{\lfloor \log_a n \rfloor^2 \times
a^{\lfloor \log_a n \rfloor}
\in \Theta\left((\log_a n)^2 \times a^{\log_a n}\right) 
= \Theta\left((\log n)^2 \times n\right)}.$$
This MSE link has a series of similar calculations.
A: This is amenable to analysis by the Akra-Bazzi method. The calculations go like this, using the notation of the Wikipedia article:
\begin{eqnarray*}
k & = & 1 \\
a_1 & = & a \\
b_1 & = & 1/a \\
g(x) & = & x \log x \\
h(x) & = & 0 \\
p & = & 1 \Leftarrow a_1 b_1=1 \\
T(x) & = & \Theta \left ( x \left ( 1 + \int_1^x \frac{u \log u}{u^{p+1}} du \right ) \right ) \\
& = & \Theta \left ( x \left ( 1 + \Theta \left (\log(x)^2 \right ) \right ) \right ) \\
& = & \Theta \left ( x \log(x)^2 \right )
\end{eqnarray*}
This may not help you that much, as you may not be able to prove that the Akra-Bazzi method works.
