How do I fix this problem and use X over ssh?

You need to have the xauth program installed on remote system. The xauth command is used to edit and display the authorization information used in connecting to the X server. You also need $HOME/.Xauthority default authority file.

Install xauth

Type the following command to install xauth under Fedora / RHEL / CentOS / Scientific / Red Hat Enterprise Linux:
# yum search xauth
# yum install xorg-x11-xauth
If you are using Debian / Ububtu Linux, enter:
$ sudo apt-get install xauth
The above command will install xauth and required libraries on the remote system. Now, you can connect using ssh as follows:
$ ssh -X user@s42.nixcraft.net.in
OR
$ ssh -X -C -c blowfish-cbc,arcfour user@s42.nixcraft.net.in