If you have an Xbox one and an Xbox 360, try using the console you didn't use to change the tag originally to claim it. The same thing has happened to me, if you change your tag on one console and try to switch it to another account on the same console, it will still register in the system as being taken. If you're afraid of losing the tag, you may be able to put it back on the original account. I've had to do this before.