I figured Teemo was AP, since it counters the current meta so well (like you said, most bot champs don't put as much emphasis on MR early on), but I wasn't sure about Naut, since I'd never played him. Armor yellows, MR blues and MS quints are pretty much standard on most of my builds, so I guess what I was really curious about were the reds. I have since bought Naut and jungled with him pretty effectively, using AS marks. If I were going bot lane though I'd probably change it to either Magic Pen or Armor. Masteries seem interchangeable, so I'm not worried about that anymore. And item build seems pretty straightforward when you talk about support.

I don't know, I guess I just thought that, with the strange combo, maybe both of them were building differently. I didn't think it would be that simple. Definitely want to try it out sometime though. Just need some spare change to get the skins.