If you haven't specifically flashed the stock deodexed rom, it's odexed. You'll need to flash the stock deodexed rom to be able to theme. The themes will need to be made specifically for stock, Sense 2.1/3.0, CM7/AOSP and MIUI themes won't work.
If you want more themes, you'll be better off flashing a custom rom. I'm not sure about the availability of Sense themes, but CM7 and MIUI have theming built in. These are both AOSP roms, they're not Sense which is what you're used to. MIUI is my personal favorite, and definitely the most themable.
You can always make a nandroid backup and try out different roms/themes. If you don't like what you flash, just restore your backup or keep flashing until you find something you like.
Sent from my Evo + MIUI using Tapatalk!
Hboot 2.02 S-Off
Amon Ra recovery
More stuff that I'm too lazy to figure out and type.
MIUI 2.3.2_b1 ES (by Swiperat)
Extended Settings Mod
Tiamat 4.1.0 SBC
My wallpaper collection
If you think I can help you with something or need me to elaborate on a post then feel free to pm me. I'll try my best to help you out.
Oh, and I have a vagina. Fear me :P