It's not the fact that he had killed kids, it's the reasoning behind it.
The Tuskens were killed in a blind rage, which he was remorseful for almost straight away. He killed the younglings in calculated cold blood under instructions from Palpatine only moments after he had informed Mace Windu that Palpatine was the bad guy. Remember that Anakin was still on Mace's side. He only reacted to thinking Palpatine was going to be killed (and lose info on keeping Padme alive).
He went from a confused kid to the Terminator in an instant.