One of our dogs came from my aunt and uncle who bred him, sold him, then the family moved and they returned him to the breeder. Unfortunately, he fought with their other dogs, so they passed him on to us because our dog had recently passed away and this was his nephew and grandson of the one we had before that. Wow, that was a long, confusing, pointless story. Anyway, his name when we got him was Snoopy. Which would have been okay if he was a beagle, but he was a Shetland Sheepdog. We decided to change his name, but were told it had to be something similar, so we made it "Sparky."
Maigee was named Tellula(h) by the shelter where I got her (and yes, the h was optional, on some of her papers, not on others). Obviously she hadn't been named that for long, she was picked up on January 30 and I brought her home on February 7. Prior to that, who knows what her name was. She adjusted to her new name very quickly though. Well, once she got over her kennel cough. Before that, she didn't respond to much at all. And now she responds to various random nicknames that have stuck over the past few years. The ones I can think of right now are Dog, Squeak/Squeaker/Squeaky, Mag, Fluff Butt (this is a new one). If I remember right, Kirsten convinced Cole that his name was Fruit Loop (or some similar cereal brand). So it isn't really that hard to change names, but like Magestaff said, they may still respond to similar names to their previous one.