Yes, that sounds strange enough. What a appears in your terminal as your "prompt" is what a variable called PS1 gives (a variable in your shell, bash right?). If you only want to change your prompt, then just changing this variable would be enough. You could try:
which would give you a new I_M_SO_COOL$ prompt (of course you can change this to whatever you like).
But of course, it is strange enough to have your prompt changed in the way you are saying.
You could try
to check if your hostname is really being used (which probably will...).
which will return the name of your host. If this was changed for whatever reason, you should change it back, as alan_ri says, by changing your host's name again. You should search for whatever file sets that variable, and change it. According to your distribution, the file where this file will be differs a bit, but I think it should be in /etc directory. So if the file is not /etc/hostname, you might
cd /etc; search -name "host*"
to search related files, and if you find somewhere written ubuntu, just change it to fedora or whatever name you like.