Have you checked the VM's BIOS?
I second that, Check the boot order in BIOS. Make sure your CD-ROM is put first. Insert your windows setup CD and reboot the VM. It should boot from the CD.
As for MS-VM and VMWare, I personaly find VMware more atractive and feature full. Specialy that snapshot feature. Sure both should be able to run any OSes, I tried setting up Windows on both and both work.
