There is a Bug filed called "Can't debug Android App":
In one of the comments someone mentions that you'll need to manually update the AndroidManifest.xml file to add the attribute
To the Application tag.
This gets the Application deployed and starts it up. But looks like the debugger still can't attach.
And it also looks like the Manifest gets autogenerated and needs to be updated each time you try to debug. Hopefully there is something one can set to adjust the automatic generation so you don't have to edit that manifest each time you need to deploy.