The problem in my case is that although I "imported my publish settings" using the powershell script GetAzurePublishSettingsFile, I am the admin of two subscriptions and this call automatically downloads both and therefore uses the first one by default. I didn't notice this at the time but it meant I was deploying using the wrong subscription and when it wanted to create the storage account I had specified, it already existed in another subscription so it couldn't create a new one.
The answer is (unsurprisingly) to specify the correct subscription in your call to Publish-AzureServiceProject using the Select-AzureSubscription cmdlet. You can find the name in the downloaded publish settings file and copy it across. I created a simple Powershell script to avoid having to repeat this:
Select-AzureSubscription "Windows Azure Bizspark 1111" Publish-AzureServiceProject -Location "North Europe" -StorageAccountName something -Slot Production