Changing toe Grass/Fire/Water thing would be thinking too small. What they should do something is to stop recycling the same storyline they have been using for the past five generations now.
You mysteriously always start out in the same town as a professor who is more than willing to give you a Pokemon that can never be caught anywhere else. You are sent across the region with a Pokedex, seeking eight gym badges and the championship. Along the way, you meet a villanous team that you defeat over and over. You finally quell and disband them between your 7th and 8th badge. You fight your way through the league and fight the champion who is usually somebody you've seen before, and then they induct you into the hall of fame.
Why change the types of starters when you can get rid of starters altogether? What about a Pokemon game where you have to catch things yourself (like in a safari zone), where things aren't always handed to you?