Why $T(n)=6T(n-1) + n^3$ has such a mess solution? I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^3$, and so on.

The formula as I understood it is: $\sum_{i=0}^n 6^i(n-i)^3$.

After entering this in Wolfram, the result is:

$$ \sum_{i=0}^n 6^i(n-i)^3 = \frac{1}{625}(-125n^3-450n^2-630n+366(6^n-1)). $$

And it doesn't look like a valid solution. Did I miss anything?
I'm not sure why you think this solution is invalid. It implies that
$$
\sum_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n,
$$
and in particular,
$$
\sum_{i=0}^n 6^i(n-i)^3 = \Theta(6^n).
$$
You can also check it for particular values of $n$.

For example, when $n = 0$ you clearly get zero, and for $n = 1$ you get
$$
\frac{-125-450-630+366 \cdot 5}{625} = 1 = 6^0 (1-0)^3 + 6^1 (1-1)^3.
$$