Both Nattorei and Shaymin-S serve different roles, anyway I've been having great success with the
Nattorei @ Leftovers
Impish
EVs: 252 HP / 252 Def / 4 Atk
Protect
Spikes
Power Whip
Leech Seed
Probably not the ideal EV spread, but it's working out well for me initally.
Perhaps you could remove Spikes for Gyro Ball? I understand Nattorei will no doubt force a lot of switches, but Spikes will most likely only be used once or twice, and though that is enough, Gyro Ball makes sure you don't get walled by Dragons in particular. Salamence, Ononokusu, Sazandora, and Dragonite all laugh at Power Whip from such a mediocre attack stat and can retaliate with their Fire-type attacks (which Onono lacks,) or they set up because you only Seed them. Not to mention, Spikes only affects Ononokusu. Maybe get Spikes somewhere else OR put this guy on a Gravity-based team. That would be magical. The various Flyers and Levvies will all have a very difficult time switching in and out with SR and Spikes support.
Aside from that, I would love Gravity Supporter Nattorei. Maybe something like:
Nattorei @ Shed Shell
Sassy (& 0 IVs in Spe)
252 HP / 60 Def / 196 SpD
~Gravity
~Spikes
~Gyro Ball
~Leech Seed / Thunder Wave / Power Whip
As soon as I get B/W I am making a Gravity team because it seems more deadly this Gen than in the last. Perhaps a new way to stall? A whole new level of phazing? With all the new pokémon, I think entry hazards would become more of a threat and hindrance than before [/theorymon]. Nonetheless, the support this guy will bring is unmatched. When paired with a synergizing phazer and spinblocker such as Heatran and Burungeru respectively, this set could be devastating. Other stall-ish pokemon and Gravity-abusers are welcome on the team, but I see the former two and Nattorei being a great F/W/G core for semi-stall (or whatever you wanna call it).
Any thoughts on Gravity Nattorei?