Obviamente, o executável binário gerado pelo PyInstaller no Linux só roda no Linux e não em outros sistemas operacionais como o Windows. A extensão do nome do arquivo é irrelevante aqui.
De acordo com o FAQ do PyInstall , você também não pode usá-lo para fazer a compilação cruzada para diferentes plataformas, mas executando o PyInstall dentro do Wine é suposto para conseguir o que você quer:
% bl0ck_qu0te%Pelo que entendi, você precisará instalar o PyInstall dentro de um ambiente Wine como faria no Windows e em seguida, use-o como faria em um sistema Windows nativo. Consulte " Como posso instalar software ou jogos do Windows? " para obter uma visão geral de como começar a usar o Wine no Ubuntu.