Gnome Desktop is Broken

The Gnome stopped working on our server running RH Ent. 5.
Users are running X11 servers on their Windows PCs and connecting to their desktops on the server via ssh clients.
Users can run something like 'xterm' on their PCs and it will open a new terminal window. When they are trying to run some Gnome applets (gedit, nautilus, etc.) it returns the errors: "The application ,nautilus has crashed", "The application gnome-power-manager has crashed", etc.
If I am (as a 'root') connecting to the server's console and trying to run gedti - I am getting the same bunch of errors.
I was playing with gdm for few days trying to fix things, no show. I even rebooted the server, the same thing.
As a temporary solution I had users connect to their KDE instead of Gnome and it's working but eventually they will need Gnome.
Can someone please point me to the right direction.