What would you have done differently? Frankly, it seemed pretty principled to me -- enough to where I wouldn't be comfortable Monday quarterbacking.
What you can do is use libraries like six to make code run just fine in both versions, and six-ify on a per file basis. This works pretty well.
The easiest things can be done by automatic translation, like 2to3.
The remaining parts get increasingly difficult, because Python 2 objects have to know how they are interpreted in Python 3, and vice versa.
A simper step would be to write an AST transformer to instrument Python 2 code and identify the non-Python 3-compatible uses of, for example, keys() and values(). That's almost as hard as writing a Python 3 implementation in Python 2, and I couldn't convince myself that it made financial sense given that it would still miss a lot of corner cases.