I've seen the same behaviour from Populous: The Beginning.
The retail (v1.00) and patched (v1.01) versions both fail to launch until Win2k - the process briefly appears in the task manager, then exits without anything appearing on the screen. However, the demo version works - go figure!
Running under AppCompat results in exactly the same error message: a messagebox containing the text "MSVCRT.DLL for Win32. Error: MSVCRT.DLL is not compatible with Win32s", followed by a crash (it takes out AppCompatt too).
I can cast a little bit of light on this (I'm a Win32 developer), though I'm afraid I don't have a solution.
MSVCRT.DLL is the Microsoft Visual C++ Runtime Library shipped with (at least) Visual C++ versions 4.0 through to 6.0, and packaged as an OS component in most 32 bit versions of Windows. It's a protected file under Win2k and WinXP. I can say with a fair degree of confidence that replacing this file with a newer version will not help (I'm running Win2k SP2 with Visual C++ 6.0 SP4).
Win32s was a way of running 32 bit code on Windows 3.1 - in effect a port of a subset of the Win32 API to Windows 3.1. I'm inclined to think that this error message is a side effect of the real problem (whatever that is), since the game in question isn't available under Windows 3.1 - it's targetted at Win95/98 with DirectX 6.
Anybody out there got any ideas?
