Old error message is misleading. It implied that there are objects that can be converted to str implicitly. This was true in Python 2, but is false in Python 3.

New error message conforms with TypeError messages produced by PyArg_Parse*(). It is the same in a number of str methods. It doesn't conform with the error messages for other produced by concatenating other types. But different messages are generated for different types:

>>> b'' + 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can't concat bytes to int
>>> a = bytearray(); a += 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can't concat int to bytearray
>>> [] + 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate list (not "int") to list
>>> a = []; a += 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not iterable
>>> import array; array.array('b') + []
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only append array (not "list") to array
>>> import array; a = array.array('b'); a += []
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only extend array with array (not "list")
>>> import operator; operator.concat(1, '')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object can't be concatenated

I think it would be better to unify them all.

I'm not sure that this change can be considered as a bug fix rather than an enhancement. Leave this on 3.6 release manager.