execute o programa pelo terminal e veja o que aparece. É só digitar "wine caminho_do_programa". Provavelmente, o "caminho_do_programa" começará em "/home/seu_usuário/.wine/drive_c/Program Files". Vou dar um exemplo de como eu executaria, via terminal, um programa meu do wine:
wine "/home/vinicius/.wine/drive_c/Program Files/Microsoft Office/OFFICE11/WINWORD.EXE"
As aspas duplas antes e depois do caminho do programa são importantes por causa das pastas com mais de uma palavra ("Program Files", por exemplo), para que o sistema não entenda como dois comandos diferentes. Proceda dessa forma e você poderá ver qualquer mensagem de erro no terminal.
Boa sorte!