Background Story
Pokemon East and West take place in a brand new Region named Elcipa. The Region of Elcipa is divided into two Independent States. East Elcipa and West Elcipa.(Hence the name) These two states are locked in a war between each other using Pokemon as their foot soldiers. There is rumored to be two Legendary Pokemon capable of leading an army to Victory, Arcyx and Oceiro. While this war commences, there are many franticly searching for these Pokemon.
Your Story
Your Character(Boy/Girl) is having their 10th Birthday and your parents promise to take you to the pokemall to buy your first Pokemon.( One of the Three Starters,because they are on sale) You pick one and then you go home. The next day, you wake up to find Professor Redwood waiting for you. Professor Redwood wants you to collect Data on all the Pokemon in Elcipa for "secret government uses"(you will find the answers in the game) so the Prof. can present the Data to his superiors. You receive the P.D.C.D. (Pokemon Data Collecting Device) to do your survey of the Region.
-
Okay, a couple things here.
First and foremost, the main character should NOT be ten years old. I realize that most people view that as canon for becoming a pokemon trainer, but realistically, that would not happen in any world. I mean, think about it: Sending a 10 year old to gather data for "secret government use"? That's about as useful as strapping explosives to yourself and detonating them in an attempt to fly. Who knows, maybe the explosion will thrust you into the air?
What makes the pokemon series so timeless is the fact that you aren't playing AS a character, it's that you ARE the character. I like the idea of it being the main character's birthday, and that they will get a pokemon for their birthday gift, but it should not say anywhere that the main character is 10 years old. If you don't say the character's age, it allows the player to easily take the role of the main character and enjoy the story more closely than they would as opposed to playing as someone else. That's why main characters in the pokemon games never speak - they're just the player's avatar in the pokemon world.
Another thing is, you're leaning toward a Team Magma/Team Aqua-esque battle here, which is silly, considering the story will remain in a deadlock in terms of this war. Furthermore, if a war is raging, the region must show how the war has destroyed everything. People must be dead, death must be witnessed (or at least hinted at) for a strong storyline.
Another thing to help make the story stronger would be, if the player starts in one portion of the region, the people of that region should express patriotism for THAT particular portion of the region. When the player enters the opposite side of the region, the one they didn't start in, the people should hold opposite patriotism, but should not be hostile to the player. They should assume that the player character is from
their portion of the region and bare no hostility toward them. Sorry, I realize my wording is a bit confusing.
-the purpose of the above concepts is to show that, while torn patriotically and in terms of viewpoint, both sides in this war are still people and pokemon. A very cliche moral, but one that works if done right.
On the topic of war; why are they at war? There needs to be a powerful political aspect to this story, some glue that holds the idea of "war" together, otherwise, it's pointless. Some event has to be the cause of the war, or a series of events, perhaps mistaken events, or the loss of important figures or pokemon for the people which caused the region to seperate themselves and go to war.
I also think it beneficial if you set this in the past, before generation 1 games, as war using pokemon would be more believable if it were before the advent of some technology in the gen IV or V games.
I believe you should have some sort of insurgence as well; a "Team" that is actually anti-war and attempts to stop the war, sometimes involving the player character.
I doubt, during a time of war, regular pokemon gyms would exist.
Especially considering the "professor" of the region sends the main character out to gain information for that side of the region's government-- they'd need that information as quickly as possible, and thus, would not allow the player character the leisure of taking on gym battles as a portion of their "quest". Plus, a deviation from the gym battle idea would be incredibly refreshing. That isn't to say you shouldn't have tests of the player's strength throughout the adventure. I just think it wouldn't fit in the form of "gym" battles. Maybe run-ins with army generals or powerful trainers or something that are required in order to move the story along.
I also think that the "professor" should not only come into light as a bad guy for using the player, but I think in the end, both sides should be double-crossed by some interloper who wants to rule the region for him/herself. When the story comes to a climax, and both sides are either having a final stand or about to have a final stand, the player character intervenes, and the interloper finally shows their true colors, introducing a final story arch that may act as a sort of "elite 4 / champion" battle, kind of like N and Ghetsis in Gen V.
One final thought is that, when the player chooses their gender, a boy or a girl, as well as their section of the region, east or west, whatever options they don't select are used for a rival character.
-What I mean is, if I were to select a "Boy" character and start in the "West", I'd eventually meet the "Girl" as a rival, who'd eventually turn out to be a spy (same age as the player, same kind of idea from THAT section's "professor") from the opposite section of the region. It helps the plot and also provides a rival character and some great story elements are possible with this.
Oh, also, as for the legendary pokemon that will help to win this war for either side-- the player should only be able to capture one per version, and it should be that version's mascot. They should be able to capture it at some point in the story when the player character stands up to his/her own region's army to protect their rival or something like that, possibly right before the final story climax.
These are my thoughts.
Also, the names you're using are a bit difficult to pronounce for me, and possibly for some others. Perhaps a simplification is in order.