Well, you're right, theme changing doesn't do very much to TCPMP's skin. I have the Sprint Touch, which came from the box with an HTC theme. TCPMPs buttons were virtually invisible with that theme! Also, the [X] or the [OK] in upper right corner of most apps was sort of camoufloged.
PAJAMAMIKE wrote: "...use both media programs..."
But there's way more than just 2 available. Have you tried PocketMusic? Even the free version of it is skinable, one of the many reasons why it's my primary MP3 player. The full version is like $20, but the free version has quite a lot. Both available here:
http://www.pocketmind.com/pocketmusic.htm
Edit: PS - If the buttons are too small, you can map their function to hardware buttons with most any player.