I had this problem, too. It turns out that the problem and solution are quite simple. When an Xcode user runs an app on a device using their free personal account, the Bundle ID is registered to the personal account. Then, when the user upgrades to a paid Apple Dev account and tries to create an App ID using that Bundle ID - the backend system thinks that Bundle ID has been taken.
Fill out the form here at this website: https://developer.apple.com/contact/submit/ under the "Certificates, Identifiers, Profilescategory”. I did this and the problem was solved in less than 12 hours. This was Apple’s emailed response: "When you install an app on a device from Xcode using your Personal Team, the Bundle ID is registered to that account. I have deleted the Bundle ID "com.AppVolks.Random-Ruby” so it can now be registered on your paid membership.”
Hope that helps!