I know there's been a bunch of posts about this from people all around the world, but I thought I'd add my 2 cents. My problem arose from the fact that I use a dual monitor setup. So either I use Xinerama or the NVidia / ATI proprietory dual monitor setup (it changes when I reinstall or upgrade my GFX). No setup works properly with War3 in full screen though. Plus, it just looks screwy in the aspect ratio that dual monitors provide.

Simple solution is to use Wine ./war3.exe -window and run it in windowed mode. This will use DirectX though, and behaves strangely sometimes when resizing the window. I've had really good results running Wine ./war3.exe -window -opengl though. It just, works. :)