Кажется, есть проблема при использовании pip-19.0.1, потому что, как предполагает другой ответ, использование 18.1 работает нормально.
Но теперь также выпущен pip-19.0.3 и обновление до этого кажетсячтобы исправить проблему.
Поэтому я предлагаю вам попробовать обновить pip, а затем установить pyinstaller
python -m pip install --upgrade pip
pip install pyinstaller