Hm, interesting thread. I'm a rather old pokemon player, you can see my age being 21, and Platinum (which I've not yet completed) is my first game since Crystal.
There's been some mentioning of changing stuff up, not just the typical get pokemon from prof, battle gym leaders, elite four, etc. While I do agree with this and I've only played uh, 5 games, (Blue, Yellow, Gold, Crystal, Plat), it does seem "kinda old". Thing is, it's somewhat of a winning formula, people keep buying the games, oldies like me can come back and jump right into the old feel of it, etc. Sometimes it's not good to mess with a good thing, ya know? But I do agree that it could be changed up a bit.
Removing HMs, I totally agree with. If you're going to try to restrict us to avoiding certain places find better ways. I don't want to carry an HM slave or have to put a move I don't want on my pokemon. Maybe just remove the annoying "there's an item behind x building early game, but you need the ability to y outside of battle to access it when you half way through the game." Just put the item later. Either add some sort of "HM slot", or just due it more based on typing/pokemon. Why does my Scyther need an ability in order to cut down trees when it has two giant cutting scythes? Why does my Lapras need a move in order to carry me on it's back when it was pretty much entirely designed to do so?
There's a lot of talk about whether or not to be a co-ordinator/trainer/breeder, and while I don't really know what a co-ordinator is (I think contests? haven't looked much into those and haven't watch the anime in years), some sort of open-ended stuff could be possible, or just varying storylines. Playing the same game with a different team isn't exactly highly motivating replay value. Some variety between Male/Female at least, if not for replay (playing as the opposite sex loses a bit of the immersiveness of an RPG), but for believablity. When Dawn loses her Pokedex and comes running for help, that's believable. When Lucas does it, less so. (Now that might seem sexist/stereotypical, but I mean no offense.) That can just be an example in general, their sex aside, they're two different people and as such should act differently.
The weather factor has been interesting if rather secluded, needs more varying weather patterns, not just on a few routes. Weather, drought, seasons, this is 2009, it's far from impossible and weather can be unpredicable, even on the DS, I'm fairly sure. Create a more dynamic world, add a desert, add a volcano (I can't remember if you could actually enter the one in the earlier games, it's been a while), add stuff besides grass and caves, basically. It doesn't even need to be complicated, I'm not asking for puddles that show up during rain and slowly vanish as the sun is out. Snow, all sorts of things, make it a week or two per season.
I really loved the ability to go back to Kanto in the Johto games and would enjoy the ability to continue battling. The gym system is fairly flawed though. They're supposed to be the best of the best, but when you're a novice trainer with a weak bulbasaur trashing the "best rock-type trainer" it gets a bit unreal. Also like mentioned, NPCs sometimes talk about stuff like having a balanced team (I think?), while the "best" tend to have just a single type, I think the gyms can keep a theme, but they can mix up the teams a bit. Maybe give them more pokemon (or restrict your pokemon to match theirs, like 3 vs 3, like I think was done in the anime.) Theme doesn't need to be a type either, can be more of them like Koga and his ninja theme.
Smarten up the NPCs. Don't give every single Team X member the same 5 pokemon, saying they're from the "HQ" and that they're borrowed isn't an excuse for being lazy. I know it can be hard to give 2839013 NPCs a different team, but if you're going to make 283023 pokemon,I think you're up the challenge. Have them have decent movesets as well, I hate seeing them use a weak move on me for a small amount of damage even when the levels are mostly equal. And just make them smarter in general.
Stop making new pokemon that basically fill the same role as a counterpart in a previous generation. While I know that say, Pidgeot and Stararaptor are quite different, in the early game, they might as well be the same pokemon. They're a "weak" flyer that you find at the beginning of the game. I was rather disappointed with the 3rd gen in terms of looks way back then it first came out and it somewhat turned me off of the series (though I was also in the "pokemon are kiddy" type phase mostly brought about by peer-pressure, but I digress) though I don't critise so harshly now that I'm used to them. Mix up the typing, someone mentioned unused combinations. This goes along with mixing up the entire game too, I think. (I think that the current amount of pokemon is getting a bit bloated, but there's no way to reduce it without a good deal of people complaining.)
I like the fact that the different types of pokeballs show up when you're catching and sending out your pokemon and I also like the seals. But there needs to be more with the graphical stuff. No, I'm not talking about full 3D, I'm not too hot on that, I'm quite happy with the current look of the game, personally. But, mentioned many times, certain pokemon being able to come out of their pokeball and walk with you. Split pokemon up into size types, and alow the small and medium ones to walk outside sometimes. Also base this on pokemon type obviously, something like Lapras couldn't walk outside of it's pokeball on land, though it's also a bit large too. Immobile ones like Kakuna would also be disallowed. Also base this on weather, probably not healthy for a fire type to be outside while it's raining. While a grass/water type would love it. Also change the look of the pokemon that you're surfing on. That blob in Plat is unattractive as can be.
Also, something personalwith your own pokeballs, from say, having a selection of colours at the pokemart, to having the ability to customise them even after you've caught someone. Ultra Ball default is fine for a while, but you might want to have it gold with silver thunder bolts or something. (When I first saw the Seals, I thought this was what it was, but then I read more into it and found out that I was wrong.)
Additions like psuedo-cut scenes would work. The little screen before gym/TG battles are a set in the right direction. Also make battling locations a bit more realistic. A small platform at the back of the gym isn't a good battleground.
General graphic interface changes would be okay too, colours, styles, etc. I think that player avatars could be selectable to some extent.
There's a lot more I could write, but a) this post is already long and b) they're getting into stuff that'd be more focused on older players, while the game is mostly suited for younger players. (It's arguably more difficult for a younger player to play in a more mature game than it is for an older player to get into a lighter mode game.