When you setup your computer at the time of your initial Ubuntu installation, you assign your computer a hostname. In my case, I gave it a hostname and then later wanted to change it to something else. This is accomplished in two easy steps.
, and overwrite the hostname with the new hostname. This will make it so the correct name is show when running the hostname command. Second,
, and overwrite the hostname here. This will allow you to use sudo successfully and network applications to run. This was done on Ubuntu 9.10 (Karmic).