Well, i guess that's part of the protocol philosophy. There exist cursor-like objects that would be natural candidates for being used like iterators (files are one example, database cursors are another). Choosing __next__ makes it possible to add support to an existing object when appropriate, instead of requiring an auxiliary object regardless of whether it's appropriate or inappropriate.
OK, that's clear.
To me, the former feels like the more typical Python thing to do, because it's consistent with the way all the other protocols work. So it's from this perspective that "next" without underscores is a wart to me.
For example, when something is container-like you can implement __getitem__ on the object itself, and then you can use  with the object. Some objects let you fetch containers and some objects implement __getitem__ on their own. But we don't force everybody to provide a convert-to-container operation in all cases before allowing them to provide __getitem__.
Now, weren't you a co-author of the Iterator PEP? I wish you'd brought this up then. Or maybe you did, and I overruled you. Sorry then.
But I don't think we can withdraw this so easily. It's not the end of the world.
--Guido van Rossum (home page: http://www.python.org/~guido/)