I think they must have changed the unlock conditions in one of the later patches, because I had to play Tina until I was about level 50 with her, in order to unlock Power is Beauty.
The other day, I set about grinding for the other themes, and they had all been unlocked for each character by about level 15, like Onryoki says.
I still would like them to add Gonna Make You Gasp, and Evolution - just in the interest of completion, Zack and the Training modes already have better themes LMAO - but I'm guessing we may get extended soundtracks with an eventual re-release, themes for Diego and NiCO and so on.
EDIT: Grand Style also unlocked before Mayflower, for no reason at all, for me.
For the DOA1 themes, for applicable characters, it looks like the Saturn theme consistently unlocks before the PSX one, at least.