Tente forçar o modo OpenGl no jogo ao iniciá-lo.
Para um teste rápido você pode simplesmente abrir um terminal ( Ctrl + Alt + t ) e digitar isto para iniciar o jogo forçando OpenGl
wine ~/.wine/drive_c/Program\ Files/Warcraft\ III/Frozen\ Throne.exe -opengl
Se funcionar, deixe um comentário para que possamos encontrar uma solução mais permanente