I have faced this problem before. Did you try to cat the file /etc/hosts and change your hostname ? Give a try. I did changed the localhost.domain and i lost my network connections. Try to replace the localhost.localdomain and re-try again. In gnome im sure there is a graphical way to change back the localhost, as how you changed it. Try to change back.
Do post again if that solution doesnt help.