Thanks andrewf Mr. DH Code Monkey! They upgraded my VPS and it worked like a champ. For others that are interested in setting up VNC on their VPS, below are the instructions that worked for me.
Before getting started, make sure your packages are up to date,
$ apt-get update
To install the X Window System with the Gnome windows manager,
$ apt-get install x-window-system
$ apt-get install gnome
To install a vncserver,
$ apt-get install vnc4server
To launch the vncserver,
After it starts, it will create a .vnc directory in your $HOME. If you want to run a gnome session instead of a basic twm, uncomment the first two lines in .vnc/xstartup,
# Uncomment the following two lines for normal desktop:
There were errors in the .vnc/hostname:#.log file because it could not find the "exec" command. You might have to change the permissions on xinitrc so it is executable,
$ sudo chmod 755 /etc/X11/xinit/xinitrc
After these changes are made, kill the current session and start another,
$ vncserver -kill :1
There are many vnc clients available. I use RealVNC Free Edition.