Yes; here's the multi-step process.
1) Go to http://account.live.com/acsr and do the best job possible to provide the needed info then submit it
2) Once submitted you will get an email back with a reference number
3) When rejected, get the Console ID (from Settings | System Settings | Console Settings | System Info | Console ID on the 2nd line).
4) With the Console ID and the reference number in hand, click on http://support.xbox.com/en-US/contact-us?xr=footnav#0:6:1 and select Request A Call then explain what's going on. The very next available agent will call you about this - and take the information for a UE request to get the gamertag back into your hands.