First see if your server has TCP listening turned off by executing the following command: defaults read org.x.X11 | grep nolisten. The output will read either "nolisten_tcp" = 1; which is bad, or "nolisten_tcp" = 0; which is good. If TCP listening is off, turn it back on. I did this both as root and my default non-root username, as I didn't know which one took precedence:
sudo defaults write org.x.X11 nolisten_tcp 0
defaults write org.x.X11 nolisten_tcp 0
Shut down your X11.app, then in Terminal, type xterm, and as normal, the X11 terminal should pop-up. In the xterm, enable all remote users by typing xhost +. Back in Terminal, type the following to see if the server is now listening for inbound TCP requests: netstat -na | grep 6000. You should see something like this output:
tcp4 0 0 *.6000 *.* LISTEN
tcp6 0 0 *.6000 *.* LISTEN
Now on your remote system things should be as before. Just setup your DISPLAY to point to the Mac and fire away. I assume this is persistent across a reboot, but I didn't try. The original solution was found here by Johannes Overmann.

