Songbird

The first thing that came to my mind was the old LucasArts game "Loom." I remember the music scale being integral with that game, but its been a long time. Might be worth looking into for inspiration.

As for your overall idea, it is very intriguing, but I still don't have any impression on how the game plays. You mentioned it being a side-scroller, but how does the musical scales feature in it? Are they an integral part of the gameplay or just the setting? A Mario clone would be less interesting than a more tactical game, where you use music as an ability to overcome the obstacles. For instance, if you are in the land of C, calling a C (perfect consonance) would give you one result, while calling an F (perfect fourth) would give you another, and a G (perfect fifth) would give you a third. Perhaps all the perfect consonances would be defensive, imperfect consonances would be distraction/illusion, disonances would be aggressive, etc. (My music theory is real rusty, sorry). Start the player off with a few notes and as they progress they open new ones. Plus, as you advance in the world to the lands of F and G, your current notes would no longer have the same result since the key changes. So your perfect C might become a minor sixth in the key of E or a dissonant note in the key of C-sharp.

Just realized I didn't answer any of your questions. So...
1. Yes. Yes.
2. Mobile puzzle.
3. Yes, I think people would be able to get it.
4. Depends on the gamplay, but I would get frustrated.
5. Figure out what type of game it is. You could get vastly different games from the same idea.