I had a pretty neat idea for a game, but I don't have the skills or talent needed to implement it. If anyone is interested, check it out here. I'd be interested in hearing whether this sounds like a good idea.
This sounds a little like what Tecmo did with their Monster Rancher video game. The game idea is simple. A random CD would generate a monster. The same CD always generates the same monster.
Remember, analyzing the MP3 files or music would require the music to be on the device, unless you could run a script to generate a pseudo database file that would contain the music you had on your computer to eliminate the need to keep all of your music on your SD card.
I think a little more elaboration would help solidify the idea and help a programmer take it somewhere.
Here some questions I had right away:
What did you have in mind as far as statistics?
Did you want a sample of the winning song to play after the battle?
What kind of fighting / battle system? (traditional rpg like Finalfantasy/pokemon?)