So it's not just me then. Thank you; perhaps a bug report should be made to the PyInstaller developers.
To be clear, the binary *does* work... with older distros. I don't know for sure what is, but something about newer distros (including mine, Ubuntu 16.04) prevents any binary made by the development version of PyInstaller from working (though I think the stable version is unaffected). Even a simple Hello World script segfaults in the same way. I'll do some tests and make the bug report, and if/when the problem is resolved, I'll rebuild ReTux (and the other two games I've built with PyInstaller).
In the meantime, I recommend using the plain source code. It works out-of-the-box as long as you have Python and Pygame installed.