Victor: I don't see an API change here.  A ValueError is raised in both cases, and error messages are not part of the API. (And BTW, you may call me Georg.)

Senthil: I'd like the documentation change to be a bit more explicit that a string is always returned.  Since the string must be encoded, it would also be helpful to mention which encoding to use.

The new exception message looks slightly incorrect to me: the argument can also be an iterable of bytes.