One possible reason is that the storage account created by the new portal was most likely created as part of the resource manager deployment model, while the cloud service is still in the classic deployment model. They do not fit well with each other. You can read a little more at https://azure.microsoft.com/en-us/documentation/articles/resource-manager-deployment-model/ . I do not think the cloud service can use the resource manager storage account for deployment.
In the new portal, look at the All Resources blade. If the vault account has a green icon, this is the resource manager account. If the vault account has a blue icon, this is a classic account.
Create a new vault account as a classic account by creating it on an older portal or using the drop-down list on the new portal before clicking the "Create" button on the client that speaks about the vault accounts (before you provide the account name records, etc.). As soon as you do this, I think that showing your account will appear as an option for deploying a cloud service.
Also note that if a vault account was created immediately before trying to select it, it may take a minute or two to become visible as an option.