First, to get rid of the popup in Gnome, edit /etc/hosts and add your machine name to the end of that row you gave. Ie, you said your machine name is paul-cellar.
127.0.0.1 localhost.localdomain localhost
Now what do you mean when you say you can't start any other program? Have you tried launching one from a terminal? Is it EVERY program, or just some? If it's just some, are they programs that use the network? Try this: open up a terminal and issue a "/sbin/dhclient eth0", and then type "gedit" in the terminal. See if an editor pops up. If not, do you get an error message?
127.0.0.1 localhost.localdomain localhost paul-cellar