Ok, consegui fazer isso funcionar com o método a seguir. Eu ainda não sei como "consertar" os problemas, mas isso parece ajudar a evitá-los.
1) Se uma versão do programa estiver instalada no Wine, remova-a usando os "Programas de desinstalação do Wine".
2) Adicione o PPA da Equipe de vinhos do Ubuntu às suas fontes:
sudo apt-add-repository ppa:ubuntu-wine/ppa
3) Atualize para o último Wine (atualmente 1.5) com dist-upgrade
sudo apt-get update
sudo apt-get upgrade
sudo apt-get dist-upgrade
4) Verifique se qualquer versão antiga do programa foi desinstalada no Wine usando os "Programas de desinstalação do Wine".
5) Reinstale o programa usando os "Programas de desinstalação do Wine". Existe uma opção para "Adicionar" um programa. Use isto para selecionar o .exe e instalar.
6) Repita os passos 4 e 5 até que funcione. Para mim, funcionou pela segunda vez.