Py3 should have simply started to warn when you used "bla" without u"..." or b"...", and so on. To clear up the bad code. Then later ... maybe 10 years later, make "..." equivalent to u"...". Maybe.
IMO the real problem is the near complete lack of static checking that you fixed it with. Sure, modern Python + mypy can do a credible job finding wrong-string-type bugs, but legacy Python 2 codebases don’t have the right annotations.
I do wish I could tell Python 3 to error out if I accidentally put a str and a bytes in the same dictionary as keys.
To gracefully deprecate this behavior, you could start by generating a warning each time an implicit coercion is done. Next, make implicit coercion raise an exception, but provide a way to suppress it. Finally, remove the ability to suppress the exception.
As the GP suggests, you'd do well to similarly deprecate unprefixed strings.
This would all be pretty confusing to explain if you were renaming the string types at the same time, as Python 3 did. I think that's an indication that you shouldn't rename the types. You could deprecate `str` and just use the names `bytes` and `unicode`, which go nicely with the `b''` and `u''` mnemonics anyway.
Python 3 also changed the type of string used for Python identifiers. You'd need a strategy there as well.
It might be convenient to have some type-checking `dict` variants in the stdlib, but I think it's a separate issue from addressing the coercion issue.
It’s interpreted code, ffs. It’s not like you have pre-compiled binaries you need to stay ABI compatible with (like Microsoft did when they introduced TCHAR and co).