All that matters are hats and shirts.
P(red hat, blue shirt) $= \frac13\cdot\frac35=\frac{1}{5}$
Do this for the other combinations where hats and shirts are different colors. Then add the resulting probabilities.
There are four types of legitimate sequence of length $n$:
Type $A$: the last four colours are distinct,
Type $B$: the second from last colour is repeated later in the sequence,
Type $C$: the third from last colour is repeated later in the sequence,
Type $D$: the fourth from last colour is repeated later in the sequence.
A length $n$ sequence of type $A$ may be extended uniquely to one sequence each of type $A,B,C,D$ of length $n+1$. Sequences of the other types may be extended uniquely to just one sequence of length $n+1$ of the following types:$$B\to C\to D\to A.$$
Let $A_n,B_n,C_n,D_n$ denote the number of length $n$ sequences of type $A,B,C,D$ respectively, each divided by 24 (to keep the numbers small). From the above we have:
\begin{eqnarray*}
A_{n+1}&=&A_n+D_n\\
B_{n+1}&=&A_n\\
C_{n+1}&=&A_n+B_n\\
D_{n+1}&=&A_n+C_n\\
\end{eqnarray*}
Writing $A_n,B_n,C_n,D_n$ as a column vector and starting at $n=4$ we get:
$$
\left(\begin{array}{c}
1\\1\\2\\3
\end{array}
\right)
\to
\left(\begin{array}{c}
4\\1\\2\\3
\end{array}
\right)
\to
\left(\begin{array}{c}
7\\4\\5\\6
\end{array}
\right)
\to
\left(\begin{array}{c}
13\\7\\11\\12
\end{array}
\right)
\to
\left(\begin{array}{c}
25\\13\\20\\24
\end{array}
\right)
\to
\left(\begin{array}{c}
49\\25\\38\\45
\end{array}
\right)
\to
\left(\begin{array}{c}
94\\49\\74\\87
\end{array}
\right)
$$
Adding the values for $n=10$ and returning the factor of 24 we get:$$24(94+49+74+87)=24*304=7296.$$
This was quick to do by hand for $n=10$. However the general solution will be a linear combination of $n$'th powers of the roots of the polynomial $$t^4-t^3-t^2-t-1.$$
Best Answer
The number of ways to color the shoes so that three pairs are odd-colored is $$ N = \text{(number of ways to pick three pairs)} * \text{(number of ways to color each odd pair)}^3 * \text{(number of ways to color the one remaining pair)} $$ which is $$ N = C(4,3) * (12)^3 * 4 = 4 * 12^3 * 4. $$ It looks like you forgot the fact that the remaining pair (whose shoes are the same color) can have any one of four colors.
Combined with the case where all four pairs are odd-colored, the answer then works out to be $28 * 12^3 = 48384$.