Double-check your python! It might not be the version you expect. On my system, python was symlinked to python3.5, even though sys-apps/portage (which provides the portage Python package) didn't yet have a target for Python 3.5. Argh!
At this point, you won't be able to rebuild portage with different targets (because emerge is broken), so check all of the installed Python versions (or dig around in $EPREFIX/usr/lib/python*/site-packages) until you find one with a portage package. If you have a working eselect (I did), you can use it (see eselect python help); else, you can probably get away with just manually changing the symlink. Portage worked fine for me after this.
As for the Prefix bootstrap…it seems that if you just run the script interactively again, it'll start allll over again, right from the beginning. I didn't want to start over, so I switched to the “manual” bootstrapping process and picked up at stage three, where the script had failed. I'm really not sure why this method is recommended against, given that the bootstrapping script does all the work, just like in the recommended method.