Do you mean, like, if each nature had a list of moves that was available to all Pokémon with that nature, or if each nature had just one signature move that was only available to Pokémon with that nature, or if each possible combination of Pokémon and nature had a bonus move? All three would be… problematic, put it that way. The last would be awesome but would require an absolutely ridiculous investment of time on the part of the designers. The first two could help, but I’m not sure how you’d work them. For a lot of Pokémon it just isn’t going to make a difference. Consider Rhyperior – Rhyperior actually has a pretty awesome special movepool already, but that doesn’t really tempt people to keep a Modest Rhyperior, or use its special attacks over its physical ones. What could you possibly give to, say, an Adamant Alakazam that will make those extra points of attack more useful than the lost points of special attack? And if you do find something that makes a difference, wouldn’t it be far more powerful in the hands of an Adamant Dragonite or Scizor? On the other hand, if you’re giving your Adamant Alakazam something that makes its special attacks more useful to compensate for the penalty (and, again, I’m really not sure what this could be)… isn’t that just a roundabout way of making natures count for less? Why not just remove natures entirely, or remove their effects on stats?
In short… I approve of the direction here, but I think it would take a truly monumental amount of work to make it produce the right sort of effect.