Ok, I believe I have the answer to the issue.. Seems like this login dialog lets you log in using the Azure AD accounts, but also using Microsoft's accounts. And if you log in using the Microsoft account, it will give this error (even if this MS account has full access to your Azure account).
The solution is to go to the Active Directory in Azure and create a brand new account, mark it as a Global Administrator, then use that to log in when prompted in Visual Studio.
Microsoft has a write-up on the issue, describing the steps to go around it here: http://www.cloudidentity.com/blog/2013/12/11/setting-up-an-asp-net-project-with-organizational-authentication-requires-an-organizational-account/