I've hunted around, and I can think of two things.
1. Terminal is weird. It doesn't respect the hostname set in the Sharing pane, but if you issue the command
sudo hostname <new host name>
quit Terminal, and then reopen the application, the new hostname should appear. From what I can tell, the name in the Sharing pane is the one displayed on the network. I don't know why the two names are disconnected in Leopard.
2. It may be the case that your computer, when connected to the network, is assigned a hostname by the DHCP server. If so, then you need to contact the system administrator and request that your hostname be changed at the server level.
'Terminal' app is a bit different. The default prompt shows the hostname as it resolve from DNS (or whatever service you use to resolve hostnames).
You can do a 'man bash' to see the manual page for the bash shell (the man page for bash is very long) and keep paging down until you find the definition of 'PS1' (which is the default host prompt for the bash shell). You can type (in the Terminal window shell prompt) "echo $PS1" to see the current value of the PS1 variable. Mine looks like this:
The "\h" part resolves to display whatever the 'hostname' command would have printed UP TO THE FIRST "." (ie. it wont display the domain name. It's as though you typed 'hostname -s' in the terminal to view the hostname.). If you changed it to "\H" (upper case 'H') then it would display the entire hostname.
You can use the 'hostname' command to change the hostname, but this will not be saved permanently (if you reboot it will revert back to whatever it was).
Since the displayed hostname is actually based on DNS (or whatever network name service you happen to use) if someone wanted to contact your computer they could use that name or they could use the the name you provided in the 'Sharing' panel of system preferences.
For me the Terminal echoes whatever I put in the computer name field, regardless of whether or not I'm connected to a network. This guy's problem is that the terminal name is not changing, and I suspect something in his OS X configuration is preventing the computer name he inputs from being written to the configuration file that defines the hostname, so when bash looks up \h for the hostname, it doesnt get a changed value. This behavior is unlike my system, which does change the hostname according to what I type in for the computer name.
I think it is too late to avoid the reinstall and it will not solve your issue, but you can try the following.
Go into your network settings and change "using DHCP" from dynamic to "Using DHCP with manual address" input a new address and that should fix it. The culprit is the router that it is pulling the old name therefore forcing the router to clear its "cache" will change the name, also restarting might work. The end result is that having the name be different is of no consequence except to us people that like things neat.
Are you trying to change the short account name? If so, it cannot be changed. I think this is the name that appears in Terminal.
You can right click on the name of the hard drive on the desktop and change its name.
You can go into System Preferences and change the name of the shared device by clicking on "Edit" button in the Sharing window.
Are you trying to change the short account name? If so, it cannot be changed.
In Leopard, you can change your shortname but it is to be done with extreme caution.
Click padlock & authenticate to unlock (if locked)
Right-click name of your Admin account in left-hand list.
Click Advanced Options.
Stuff you can change:
Like I said, this requires extreme caution (read warning at top of that window).