Change Hostname in Ubuntu

I had this problem where the hostname I had chosen was the same on another Windows machine on the network. Therefore, I was unable to browse the network. I wanted to change the hostname so I tried the following:
sudo hostname mybrandnewname
But it would not change. It would say the name had changed but after a reboot the old name would be restored. So people at Ubuntu Forums helped someone in the same predicament. The user was unable to change hostname. I followed their instructions and here they are
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/network 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.