I can confirm CMBO on VMWare and nothing under WineX.
As far as what a virtual machine is. Stop and think a bit.
Okay, now that you have it figured out, here we go with a much more technical discussion. There will be a fair amount of history, but I think it is all interesting. If you don't skip to the paragraph that starts "Anyway, the upshot is"
The modern computer is a mixing of ideas from Von Neumann and theory of Turing. Turing (working on a tough problem in math) provided a well-defined (in math) definition of the word computation by describing a machine with a base set of characteristics. He proceeded to show that this definition both meshed with the intuitive notions of computation, and provided a good framework for discoveries into the nature of math. One of the things they take you through in a CS course at a Uni are the proofs that more complicated Turing machines can all be simulated by the base turing machine. Any language or computational structure that is capable of being a turing machine is called turing complete.
Anyway, the upshot is that since any modern computer is capable of simulating any other computer (given enough time), people have written programs to do so. A virtual machine is a program with the purpose of simulating another machine.
Examples
Java. In order to be able to "run anywhere" java defines a machine that all Java interpreters simulate to run the software.
bochs. Bochs is a x86 simulator for a variety of platforms (say, allowing you to run x86 code on a Max)
VMWare. VMWare is also a x86 simuilator, but it operates differently. Instead of simulating the whole machine, it simulates only sections, dropping the rest through to the core hardware. This allows it to get a speed boost as the bare hardware can do a lot of the work. The problem is that you can only run x86 code on an x86 machine. BTW, this is a godsend for anyone that has to test code written for windows as you can do all your testing on a hermetically sealed operating system while still having your development environment available.
UltraHLE. This is an interesting case of what is called dynamic recompiling. It takes the code it is passed, and recompiles the code so that it is native to the new processor. This is an inherently impossible task, but if you do it "well enough" you can play N64 games on your PC.
WineX is often mistaken as an emulator or virtual machine. WineX is actually a completely different breed. WineX is an implementation of the Windows API for Linux. In particular, the DirectX sections. This is a vital distinction because if the WineX implementation is more efficient than the original implementation, it will actually perform better. Case in point, back in the day, I would get 20% better framerate running UltraHLE -> Wine -> Linux than running UltraHLE under Windows.
Enough babbling. Right now CMBB under linux just ain't goin' ta work. Here is to hoping that CMX2 is written using something like libSDL and OpenGL to make a linux version a possibility (and make the Mac version much simpler)
Jeff