I had the same issue.
Seems like the publishsettings files related to specific sites/services/apps are always rejected.
The solution seems to be to get a publishsettings file for your entire Azure account instead, and after that you're able to access your sites/services/apps or create new ones and publish to them.
This is performed using the following steps:
. Right click the project in VS10 and open 'Publish...' (the Azure
publish settings)
. Go to the Summary tab. Here you are able to download a publish settings file related to your Azure account. This file is named something like 'three month free evaluation period 1-1-2013-credentials.publishsettings' rather than the publish settings file for a particular site, which would be named somethiung like 'mysite.azurewebsites.net.publishsettings'. Import that file - it will work!
3. Now go to the settings tab. Here you can select a cloud service (select existing or you can create a new one) and assign some settings.

. When the configuration is complete and you've clicked the Next button, VS10 will start deploying your project to the selected service. This is displayed in the 'Windows Azure Activity Log' output window in VS10.
