First, always check the wine application database
to see what experiences other people have had for the program, if any. And read the wine documentation
Next, run 'winecfg'. There you can tweak things like the type of Windows simulated (Win98,XP, etc), and whether wine tries to use its own native .dll libraries or external ones. Just load the program exec name into the application panel, and when that name is highlighted it and the other tabs will configure for that application only.
Not sure if it will work on something that has its own .dlls though. You could also try moving the .dll files to the wine "windows" system directory to see if it picks them up there.
In the end though, some applications just don't work. It all comes down to the specific needs of that program and whether the wine project has completed support for those needs.
Edit: Now he tells me. Still, it's good advice.