É possível que este seja um problema de bitness, em que você está usando um Explorer de 64 bits, mas instalou a versão de 32 bits do python? Nesse caso, o Explorer de 64 bits pode não funcionar.
Se você instalou o Windows de 64 bits, ainda é possível testar essa teoria descartando um arquivo em um script .py usando o Explorer de 32 bits, que é chamado por meio desta linha de comando:
%Systemroot%\SysWOW64\explorer.exe /separate
[EDITAR]
Como você diz que esse não é o caso, só posso oferecer uma solução alternativa para compilar os scripts .py para .exe usando uma ferramenta como py2exe :
py2exe is a Python Distutils extension which converts Python scripts into executable Windows programs, able to run without requiring a Python installation.
Pergunta: Você instalou o python usando seu instalador?