I also couldn't add my domain to Azure without the leading "www.". I realised that I should have had two CNAME DNS records set up instead of just one.
I had the following set up:
awverify.www CNAME awverify.XXXX.azurewebsites.net
But in order for you to register your url without the "www." prefix, you need to set up another CNAME in order for Azure to verify. I then added the following:
awverify CNAME awverify.XXXX.azurewebsites.net (as you can see I have added the same as above but the awverify doesn't have the suffix of ".www".
I could then verify Azure against the new CNAME record allowing me to register my url without the leading "www." with Azure.