I'm warming up slightly to the idea of this ABC.
I've re-read Amir's post, and if I found myself in his situation I would have used a combination of documenting that __slots__ needs to be ordered and at runtime only checking for a few common definitely-bad cases. E.g. for exactly set or dict (not subclasses, since OrderedDict inherits from dict) would cover most of the common mistakes: most people will use a literal in their __slots__ definition so we just need to watch out for the common literals. Those users who are sophisticated enough to use some advanced mapping type in their __slots__ should just be expected to deal with the consequences.
But the Ordered ABC, while not essential (unless you're a perfectionist, in which case you're in the wrong language community anyways :-) still fills a niche.
The Ordered ABC should have no additional methods, and no default implementations. I think it should apply to collections but not to iterators. It should apply at the level of the read-only interface. Sequence is always Ordered. Mapping and Set are not by default, but can have it added. OrderedDict is the prime (maybe only) example -- it's a MutableMapping and Ordered. We might eventually get an OrderedSet.
A sorted set or mapping (e.g. one implemented using some kind of tree) should also be considered Ordered, even though otherwise this is a totally different topic -- while some other languages or branches of math use "order" to refer to sorting (e.g. "partial ordering"), in Python we make a distinction: on the one hand there's sorted() and list.sort(), and on the other hand there's OrderedDict.