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 ?)
Run a Perl script called winecheck, to be found in Wine's tools/ directory. The latest version can always be found at http://home.arcor.de/andi.mohr/download/winecheck. Make sure to run chmod +x winecheck first before trying to execute it... (or alternatively run it via perl ./winecheck) The winecheck output will be a percentage score indicating Wine configuration correctness. Note that winecheck is only alpha, so it's not very complete or 100% accurate.
In several cases using different windows version settings can help.
This sometimes helps, too: Try to use both wine prg.exe and wine x:\\full\\path\\to\\prg.exe
Run with --debugmsg +loaddll to figure out which DLLs are being used, and whether they're being loaded as native or builtin. Then make sure you have proper native DLL files in your configured C:\windows\system directory and fiddle with DLL load order settings at command line or in config file.
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 (!), ...) E.g. some people have strange failures to find stuff when using "wrong" header files for the "right" libraries !!! (which results in days of debugging to desperately try to find out why that lowlevel function fails in a way that is completely beyond imagination... ARGH !)
Instruct Wine via config file to use either desktop mode, managed mode or plain ugly "normal" mode. That can make one hell of a 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).
Go to GameCopyWorld and try to find a decent crack for your game that gets rid of that ugly copy protection. I hope you do have a legal copy of the program, though... :-)
Running with or without a Windows partition can have a dramatic impact. Configure Wine to do the opposite of what you used to have. Also, install DCOM98 or DCOM95. This can be very beneficial.
Sometimes wine installation process changes and new versions of Wine acccount 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. For source wine distribution to configure Wine run tools/wineinstall script as a user you want to do the configuration for. This is a pretty safe operation. Later you can remove the new ~/.wine directory and rename your old one back.
Check out the Wine Troubleshooting Guide on WineHQ. Go to Google Groups and check whether some guys are smarter than you ;-) (well, whether they found a solution to the problem, that is) Go to WineHQ's Application Database and check whether someone posted the vital config hint for your app. If that doesn't help, then consider going to irc.freenode.net channel #WineHQ, posting to news:comp.emulators.ms-windows.wine or mailing to the wine-users (or maybe sometimes even wine-devel) mailing lists.
Have you used the Search feature of the Wine Troubleshooting Guide ?? (i.e. are you sure there's no answer ?) If you have, then try The Perfect Enduser Wine Debugging Guide, and of course don't forget to read the Wine Developers Guide.