Value Jet renamed themselves AirTran after one of their planes exploded. GTE became Verizon after being horrible for years.
Great hacker branding intro: http://blip.tv/file/319044/
"A brand is a const identifier."
(back story to the video: http://steve-yegge.blogspot.com/2007/08/how-to-make-funny-ta...)