> I don't want to change the kind of exception being raised (an API change from
> AttributeError to TypeError) without a really good reason.

Subclasses cannot work with the current implementation.

> In general, in-place methods are not required to return NotImplemented (for
> example, (3).__iadd__(4.5) raises an AttributeError).

AttributeError is being raised because int does not have an __iadd__ method, not because of a problem with the float operand.

> Also, I prefer the current AttributeError with its clear indication that an items()
> method is needed for duck-typing.  These kind of error messages are very helpful
> when you're trying to figure-out how to duck-type on-purpose

That's what the docs are for.

> (for example, {}.update(1) and {}.update([[]]) both provide the information about
> what you would need to do to get update() to work).

update is not a binary operation, so has more leeway in how it handles problems.

> The current duck-typeable behavior was an intended part of the design and is no
> different from a number of other methods that update in-place.

The only problem with the design is that it does not play well with others.  For duck-typeable just do a check on 'other' to see if it has an .items() method, and return NotImplemented if it does not.  Oh, and check that 'self' is Counter, and also return NotImplemented if that fails.

> At any rate, I want to avoid unnecessary API churn (and avoid contributing to
> what Guido has called "a death by a thousand cuts" for the growing list of tiny
> semantic differences between Python 2 and Python 3).

Not an issue in this case, as the 2.7 Counter does not have the in-place methods.

Here's proof of subclass trouble -- the idea is to make an immutable Counter:
---------------------------------------------
from collections import Counter

class FrozenCounter(Counter):
    """
    immutable after definition
    """
    def __add__(self, other):
        new_counter = self.__class__()
        for elem, count in self.items():
            new_counter[elem] = count
        for elem, count in other.items():
            new_counter[elem] += count
        return new_counter._keep_positive()
        
fc = FrozenCounter("abbc")
sc = FrozenCounter("bubba")
original = fc
fc += sc
assert fc == FrozenCounter("aabbbbbcu")
assert fc is not original
---------------------------------------------

and the results:
---------------------------------------------
Traceback (most recent call last):
  File "blah.py", line 20, in <module>
    assert fc is not original
AssertionError
---------------------------------------------

For subclassing to work, the fix is:

        if not hasattr(other, 'items') or type(self) is not Counter:
            return NotImplemented