Spróbuj pobrać najnowszą wersję TCPMP, z tego co pamiętam miała wgrane więcej kodeków.
Jeśli to nie pomoże, pozostaje Ci albo Android SD, albo przeflashowanie Androida NAND, i korzystanie z programów pokroju RockPlayer.