After installing Wine, you need to set the path to DLLs.
In old versions of Wine this was easy. In new versions of Wine you have to edit an obscure file corresponding to the registry in an obscure way, and it's impossible to automate this step. Yay for progress.
After installing Wine, run it once as your ordinary user (just type 'wine'). This creates the Wine local configuration in your $HOME/.wine
Edit .wine/system.reg in a text editor.
Search down for the section marked:
[System\\CurrentControlSet\\Control\\Session Manager\\Environment]
which should contain multiple lines, one of which is:
"PATH"="C:\\windows\\system32;C:\\windows"
(to confuse the issue, sometimes the path will be slightly different, and sometimes the string will have str(2): prefixed onto it).
At the end of the path, before the final double-quote, you have to add:
;Z:\\usr\\i686-pc-mingw32\\sys-root\\mingw\\bin
so that's semi-colon, the path, and the double-quote will follow. It will look something like this:
"PATH"="C:\\windows\\system32;C:\\windows;Z:\\usr\\i686-pc-mingw32\\sys-root\\mingw\\bin"
Save the file and you should be able to run command line programs using wine without an errors about missing DLLs.