Off the top of my head, and using your story but tweaking it slightly, the main character (Nathan Jones) is from a town. He gains his first Pokemon [insert starter here] and decides to battle his friend, and after the battle, the friend sets off to take on the gym challenge. You decide to do so for yourself, but when you come to a gym, it's a trap. Team Terra steals your best friend, and you decide to look for him/her.
That's my idea of how it starts. I think that Maka should be involved with a few legendary Pokemon (or just some strong and idealist Pokemon). The legendary Pokemon should then cause the end of the world or something and leave you, the main character, to fight them off while saving Maka from the three teams.
The main body should be for searching towns and places for Maka's whereabouts, but it should also be filled with suspense up until the game's conclusion.
But that's just what I think. I also need to know which Pokemon (choices) will the protagonist start with.
I also need to know what you want me to do to help with the project.