I don't think it's about Gnome; Xserver errors would refer to X server itself having problems, maybe a faulty configuration (compared to hardware, for example). If you can run Mandriva with KDE, you could install Gnome for Mandriva (I assume it's available trough the package managing system as usual) and very probably it would run just fine. If it's inside one distribution that KDE does run and Gnome doesn't, it could be something Gnoem-related, but if one distribution runs (with KDE or whatever) and another one doesn't, it's more probably distribution-specific than desktop environment -specific.
Ubuntu, for example: I take it that you meant you can't even start the Desktop (live-)cd to begin the ordinary installation. The first thing to do is to try with different settings; I'm fairly confident that with the right options (for X) it will start and work. A start step would be to select low resolution and colour depth (can be done in the boot menu of Ubuntu Desktop disc, by pressing the relevant Fn keys as shown by the help text at the bottom of the screen); usually 800x600x16 works if nothing higher won't, and selecting "safe graphics mode" might also help (instead of the topmost "start or install ubuntu"). After selecting those, before hitting ENTER for the boot, you could then press the F-something key to edit kernel parameters/commands before booting, and in the kernel line replace the word 'splash' with 'nosplash'. This causes the graphical bootup not to be used, instead you'll see debug messages which may be helpful.
After you find a correct configuration and can run the thing, get past the installation and are running the real system (or just get a text login if X won't run), you can configure the running system's X (/etc/X11/xorg.conf if you didn't know) the same way you got the installer run. After you get your X server (and therefore the desktop) running, you can then tweak the settings to get better results.