Let's do the calculations on this. I'm gonna ignore crits, because a crit at any stage will obviously kill Nattorei (and because it's WICKED hard to calculate for all those possibilities). I'll put in some calculations for crits at the end.
Turn 1: Nattorei switches in, Kingdra uses Hydro Pump (now at 7 PP).
Nattorei has a 20% chance of taking no damage and an 80% chance of taking 39% damage. Leftovers heals to 100%/67%, respectively.
Turn 2: Nattorei Protects. It goes to 100%/73%. Hydro Pump is now at 6 PP.
Turn 3, part 1. Kingdra uses Hydro Pump. PP is now 5.
Nattorei has a 4% chance of taking no damage both turns (100% health), a 16% chance of taking damage on the first turn but not the second (73%), a 16% chance of taking damage on the second turn but not the first (61%), and a 64% chance of taking normal damage on both turns (34%). Note that Leftovers are not accounted for.
Turn 3, part 2. Nattorei uses Leech Seed, with a 90% chance of hitting and a heal rate of 36 HP, or 10% of Nattorei's health. Now, we're gonna hit a TON of possibilities here (that I don't want to list out), so I'll keep it simple. There's a 36% chance of Hydro Pump missing at least once, so there's a 32.4% chance of Kingdra getting next to no chance of winning (misses at least once, Leech Seed hits) and a 3.6% chance that Nattorei needs to protect another turn and try again, setting the odds even further against Kingdra (another 20% chance for Hydro Pump to miss). There's a 64% chance of Kingdra hitting twice, ending with a 57.6% chance that Nattorei will finish with 50% health. There's only slightly over a 6.4% chance that Kingdra will win without a crit.
Now, let's account for crits. Let's assume that crit=auto kill (it doesn't, Protect can work magic). There's a 17.6% chance that Kingdra will crit at least once in three HITS, so if we multiply .576 by .176 we get an additional 10.1% chance that Kingdra will beat Nattorei. That's a 16.5% chance to win, a 41% chance to lose but hit Nattorei hard, and a 32.4% chance of it losing badly (numbers were rounded, so they won't add up perfectly). This means that the Kingdra user has to either pray for no misses and Leech Seed to miss or for a crit. That's not a good situation for a wallbreaker. I'd say that Nattorei is a good counter to Kingdra. Kefka, with all due respect, I'd advise you not gamble in the future.
Now, calculations aside, there's a few other considerations. First, prior damage to Nattorei. The slightest amount can screw up this counter royally. However, the second point is that the Nattorei user can switch it in to take a single attack from Kingdra and then stay in or switch to a Pokemon which is Water-immune (or close to it, like another Kingdra), depending on which move Kingdra uses. Finally, it should be remembered that none of this actually matters all that much in terms of balance. A counter does not mean a Pokemon should not be uber. As everyone knows, standard Specs Kyogre is completely walled by Shedinja, but that doesn't mean that Kyogre should be let into OU. All this should be taken to mean is that if you're having trouble with Rain teams, Nattorei is a strong option to consider.