I could not solve the problem with my Ubuntu 10.04.3 LTS and tried Mint 12. Problem solved now with the steps described earlier by the other users.
Unfortunately it doesn't work for me. With Ubuntu 10.04.3 LTS I get the following error message repeatedly:
==
Blizzard Downloader: Release (build 1644)
Exe: C:\Program Files\World of Warcraft\BackgroundDownloader.exe
Time: Dec 3, 2011 10:00:20.828 PM
User: ruud
Computer: 3m7m23j
This application has encountered a critical error:
ERROR #1 (0x13370001) Fatal Exception
Program: C:\Program Files\World of Warcraft\BackgroundDownloader.exe
The instruction at "0x004AA103" referenced memory at "0x00000000".