Update (2020-11-17): py2exe LIVES!!!
Apparently my pessimism a year ago (see “Update” at bottom of original post) was unwarranted. py2exe released new versions in October and November of 2020, supporting 3.5-3.8 in 0.10.0.2 and adding 3.9 support in 0.10.1.0 (dropping support for 3.4 and earlier). As long as you upgrade to an appropriate py2exe version (0.10 and higher), this problem should not occur.
Further update (2022-11-09): It looks like py2exe is staying up to date with the latest releases of CPython now (e.g. they released 0.13.0.0, a 3.11 compatible py2exe, within two weeks of CPython 3.11.0 itself being released) so it looks like you can rely on continuing support for the time being. They seem to be supporting 4-5 minor releases of CPython for any given release (the first release with 3.9 support dropped support for 3.4 and earlier, and the latest release that added support for 3.11 dropped 3.7 support).
Original Answer before py2exe 0.10 release
Python 3.6 completely redesigned the bytecode for CPython (it’s not a “byte” code at all anymore, it’s a wordcode, where all opcodes are two bytes wide instead of 1-3).
The failure you’re seeing occurs in py2exe opcode parsing code, which, given the most recent posted version of py2exe only claims support for 3.3 and 3.4, could not possibly have knowledge of, or support for, the new wordcode opcodes; they hadn’t even been conceived of at the time py2exe was last updated. The bytecode often changes in small ways from version to version that could break even Python 3.5 (given only 3.3 and 3.4 support is claimed explicitly), but 3.6 is 100% guaranteed to fail.
Update: At this point (November 2019), it’s been over five years since the last py2exe release, and by the beginning of 2020 (when Python 2 support lapses completely), it will not run on any supported version of Python (3.4 is already out of support). I think it’s safe to say the project is abandoned; find other options, e.g. cx_Freeze or PyInstaller.