Now imagine Theatrhythm Pokemon.
Catch Pokemon by playing their respective route's theme in the rhythm game, be able to level up your Pokemon to evolve them and learn moves that (actually) influence the gameplay. Challenge gym leaders and elite four members and rivals throughout the generations and have a good time. I think it could work.

http://www.youtube.com/watch?v=veabPgxwryQ
If you've never seen gameplay^