sudo vim /etc/hosts
Change the old hostname to the new one. For example, my /etc/hosts file said
192.168.168.100 oldhostname
So I changed it to
192.168.168.100 newhostname
I also edited the
/etc/hostname
file.
sudo vim /etc/hostname
It read
oldhostname
So I changed it to
newhostname
After doing the following, the new hostname stuck as required.
sudo /etc/init.d/hostname.sh stop
sudo /etc/init.d/hostname.sh start
And then logout of your shell and log back in.
sudo /etc/init.d/networking restart
You should really read hostname error not resolving for more details.
As for my original problem of not being able to browse the network, it was solved with this fix.