There are times when you've been trying everything, you even killed a cat at full moon and ate it with rotten garlic and foul fish while doing the Devil's Dance, yet nothing helped to make some damn program work on some Wine version. Don't despair, we're here to help you... (in other words: how much do you want to pay?)
Look at the output from wine --version to make sure you're running a recent version of Wine. Launch winecfg and look over the settings to make sure you have settings that look normal. Look in ~/.wine/dosdevices to make sure your c: points to where you think it should.
In several cases using different Windows version settings can help.
The following sometimes helps, too:
cd ~/.wine/drive_c/full/path/to/ && wine prg.exe
WINEDEBUG=+loaddll to figure out which
DLLs are being used, and whether they're being loaded as native or built-in.
Then make sure you have proper native DLL files in your
configured C:\windows\system32 directory and
fiddle with DLL load order settings at command line or with winecfg.
Just an idea: could it be that your Wine build/execution environment is broken? Make sure that there are no problems whatsoever with the packages that Wine depends on (gcc, glibc, X libraries, OpenGL (!), ...)
Instruct Wine via winecfg to use either desktop mode, or normal managed mode. That can make a lot of difference, too.
Maybe your app is using some kind of copy protection? Many copy protections currently don't work on Wine. Some might work in the future, though. (the CD-ROM layer isn't really full-featured yet).
Sometimes Wine installation process changes and new versions of Wine account on these changes. This is especially true if your setup was created long time ago. Rename your existing ~/.wine directory for backup purposes. Use the setup process that's recommended for your Wine distribution to create new configuration. Use information in old ~/.wine directory as a reference. Later you can remove the new ~/.wine directory and rename your old one back.
There is a really good chance that someone has already tried to do the same thing as you. You may find the following resources helpful:
Search WineHQ Application Database to check for any tips relating to the program. If your specific version of the program isn't listed you may find a different one contains enough information to help you out.
Freenode.net hosts an IRC channel for Wine. You can access it by using any IRC client such as Xchat. The settings you'll need are:
server irc.freenode.net port 6667 channel #winehq
If you have a program that requires a redistributable runtime to be installed, e.g. for mfc42.dll, Visual Basic and so on, winetricks can be used to supply this. Note, these components are subject to their own license and are not part of the Wine project. For further information on winetricks see the winetricks wiki entry.
Wine forums and mailing lists may also help, especially wine-users. The wine-devel list may be appropriate depending on the type of problem you are experiencing. If you post to wine-devel you should be prepared to do a little work to help diagnose the problem. Read the section below to find out how to debug the source of your problem.
If all else fails, you may wish to investigate commercial versions of Wine to see if your application is supported.
Finding the source of your problem is the next step to take. There is a wide spectrum of possible problems ranging from simple configurations issues to completely unimplemented functionality in Wine. The next section will describe how to file a bug report and how to begin debugging a crash. For more information on using Wine debugging facilities be sure to read the Wine Developers Guide.