The startswith method accepts both string and tuple (not list). Yet
the error message suggests that it expects (only) a character buffer
object.

In Python-2.6:

>>> "foo".startswith(['fo', 'df'])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: expected a character buffer object

In Python-3.x, the error message is different:

>>> "foo".startswith(["fo"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Can't convert 'list' object to str implicitly

Aside: why not try to convert 'list' object to tuple?

In the examples you used byte strings for Py2 and Unicode strings for
Py3. On Py3 the same example with byte strings gives an error similar to
the one raised by Py2:

>>> b"foo".startswith([b"fo"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: expected an object with the buffer interface
(vs. Py2's expected a character buffer object)

The error raised by Py2 with Unicode strings is more or less the same of
Py3 too:

>>> u"foo".startswith([u"fo", u"df"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: coercing to Unicode: need string or buffer, list found
(vs. Py3's Can't convert 'list' object to str implicitly)

If I understood correctly the C code in /Objects/unicodeobject.c, this
is because startswith checks if the 'prefix' is a tuple and, if not, it
assumes that is a Unicode string. The 'prefix' is then converted to
Unicode by PyUnicode_FromObject and if it's a list or some other object
the error "Can't convert 'list' object to str implicitly" / "coercing to
Unicode: need string or buffer, list found" is raised.

I agree that a more explicit error message would be better, something
like: "'prefix' must be a character buffer object or a tuple, not 'list'".

Aside: why not try to convert 'list' object to tuple?

If the support for lists is added, it should probably be extended to all
the iterables, but strings are iterables too, so that will create some
problem. It could be checked if 'prefix' is a string and if not assume
that is an iterable of strings, but I don't know if it's worth doing it.

Here is a proof of concept that solves the problem for unicode strings and startswith/endswith.
If during the conversion to Unicode a TypeError is raised (e.g. TypeError: Can't convert 'list' object to str implicitly), the error message is changed to "TypeError: startswith first arg must be str, unicode, or tuple, not list".
If the error is not a TypeError (e.g. a UnicodeDecodeError) the behavior is unchanged.
I haven't tested the patch thoroughly, but if this approach is OK I will prepare a complete patch.

See also bpo-10616.

The approach looks good to me. I think this issue is orthogonal to bpo-10616, since the message here needs to be modified anyway, regardless of what happens to the underlying issue.

Attached an updated patch for 2.7 with tests that check that UnicodeErrors are still raised and that the error message mentions 'str', 'unicode' and 'tuple'.

New changeset 3ceeccbc2c3b by Ezio Melotti in branch '2.7':
bpo-6780: fix starts/endswith error message to mention that tuples are accepted too.
http://hg.python.org/cpython/rev/3ceeccbc2c3b

New changeset bcbf8c3c4a88 by Ezio Melotti in branch '3.1':
bpo-6780: fix starts/endswith error message to mention that tuples are accepted too.
http://hg.python.org/cpython/rev/bcbf8c3c4a88

New changeset f393c507717a by Ezio Melotti in branch '3.2':
bpo-6780: merge with 3.1.
http://hg.python.org/cpython/rev/f393c507717a

New changeset a1a1296556d7 by Ezio Melotti in branch 'default':
bpo-6780: merge with 3.2.
http://hg.python.org/cpython/rev/a1a1296556d7

I would have used with self.assertRaises to write the tests, thinking it would be less verbose/cumbersome.

In 3.1 I had to use try/except because cm.exception is new in 2.7/3.2.
I used assertRaises on the other branches.