You may well be correct.  But just because no one reported a bug does not mean that no one is using the API.  The person using it may find it perfectly logical (and may be writing py3 only code, not porting py2 code).

However, regardless of whether we decide it is acceptable to change the behavior, it seems to me that having an interface named 'tostring' that returns bytes by default in Python3 would be a broken API.  I don't see any way around that terminology problem.