The AppDB entry you mention refers to Wine 0.9.17, which is unbelievab ly old compared to either of the two Wine versions you tested. What happens if you manually (using nvidia-settings) reduce your color depth to 16 and try running the program again? You might also consider setting the Windows version to something lower/older in Winecfg, if you haven't-- a game that is dedicated to 16 bit in that way is likely very old and may not run correctly under XP (the default Windows version under Wine). Try Windows 98 or 95 and see if that makes any difference.
