I think changing the error message is enough for the short term, and deprecation of automatic encoding is the correct way in the long term.

A text that mention "utf-8" which will likely be the correct solution definitely gets my vote, so Guidos suggestion sounds good to me:

UnicodeEncodeError("Use data.encode('utf-8') if you want the data to be encoded in UTF-8")

Andrew's and Pauls suggestions doesn't point to a solution to the problem, which I think is a great think for something this basic. Also, the error message only gets shown when latin-1 fails, so we can't use text that speaks about "no encoding" in general.