Johnny Cougar --> John Cougar --> John Cougar Mellencamp --> John Mellencamp
I first heard him when he was John Cougar. We share a birthday so when I turned seventeen (after holding onto sixteen as long as I could) and got two goldfish, I had to name them Jack and Diane.
As pldennison mentioned, Pure Prairie League came out with “Amy.” Vince Gill was a member and he went on to great things in the Country genre. I guess that doesn’t count for the OP, though.
Dinosaur —> Dinosaur Jr. after being legally threatened by a group of old rockers from SF known as Dinosaur.
For awhile, Bush went by Bush X in Canada due to another Bush. Finally, the original Canadian Bush gave Bush X the rights to go by just Bush the world over. And every one lived happily ever after. Except those who had to listen to Gavin Rossdale bellow.
Scott Weiland and Robert DeLeo, met and started a band called Swing. They found Eric Kretz and Robert’s brother Dean, and called themselves Mighty Joe Young. Right before Core was to be released, they found that there was another performer by that name. So they took some inspiration from a motor oil logo and came up with three names, Stinky Toilet Paper, Shirley Temple’s Pussy, and Stereo Temple Pirates. The last name was changed into Stone Temple Pilots.
The Thamesmen --> The Originals --> The New Originals[sup]1[/sup] --> Spinal Tap
[sup]1[/sup]There was already another band called "The Originals, so they changed their name to “The New Originals”. When the original “The Originals” broke up, the new “The New Originals” were going to change their name back to “The Originals” but they figured “Why bother. I mean, what’s the point?”.