Deploy to Azure using Storage Account created in new portal

One possible reason is that the storage account created by the new portal was likely created under the resource manager deployment model, while the cloud service is still under the classic deployment model. These don't play well together. You can read a little more at https://azure.microsoft.com/en-us/documentation/articles/resource-manager-deployment-model/. I don't think that a cloud service can use a resource manager storage account for deployment.

In the new portal look at the All Resources blade. If the storage account has a green icon it is a resource manager account. If the storage account has a blue icon it's a classic account.

Create a new storage account as a classic account, either by creating it in the older portal or by using the drop down in the new portal before you click create on the blade that talks about the storage accounts (the before you provide the account name, etc.). Once you do this then I think the account show show up as an option for your cloud service to deploy with.

Also note that if the storage account was created just prior to trying to select it, it might take a minute or two to become visible as an option.