I think you're extremely close to an awesome idea.
Instead of it being a free moving platformer, make it a forced side scroller.
Add a drum track in the background.
Then design the levels such that if played efficiently, it will play a melody.
And score is evaluated based on how close the player was to hitting say, the nearest 16th note for any given jump or other action.
So its ALMOST like a rhythm game, but the melody is not predetermined, the player is just incentivized to play in a rhythm.
(maybe that will work)