Overcloud deploy fails with ERROR: openstack Conflict occurred attempting to store project - Duplicate Entry

Issue

Overcloude deployment/scale fail with the following errors:

$openstack overcloud deploy --templates ~/templates/my-overcloud --compute-scale 3 --ntp-server 10.0.0.1 --neutron-network-type vxlan --neutron-tunnel-types vxlan

Deploying templates in the directory /home/stack/templates/my-overcloud
Stack failed with status: resources.ControllerNodesPostDeployment: resources.ControllerOvercloudServicesDeployment_Step6: Error: resources[0]: Deployment to server failed: deploy_status_code : Deployment exited with non-zero status code: 6
ERROR: openstack Heat Stack update failed.

heat resource-list f6cb421c-de01-4b80-9055-4c820a50245c
+---------------+--------------------------------------+--------------------------------+-----------------+----------------------+
| resource_name | physical_resource_id                 | resource_type                  | resource_status | updated_time         |
+---------------+--------------------------------------+--------------------------------+-----------------+----------------------+
| 0             | 11b06f99-2075-4cbe-be94-bdc1c4af83a0 | OS::Heat::StructuredDeployment | UPDATE_FAILED   | 2016-03-17T09:14:09Z |
| 1             | 28cc31ee-6c0a-46ba-ba00-edd2db6ef203 | OS::Heat::StructuredDeployment | UPDATE_COMPLETE | 2016-03-17T09:14:10Z |
| 2             | 0150f4f1-7a56-44b0-9d47-5e9f70104809 | OS::Heat::StructuredDeployment | UPDATE_COMPLETE | 2016-03-17T09:14:10Z |
+---------------+--------------------------------------+--------------------------------+-----------------+----------------------+

$ heat deployment-show 11b06f99-2075-4cbe-be94-bdc1c4af83a0

.....
.....
ERROR: openstack Conflict occurred attempting to store project - Duplicate Entry (HTTP 409) (Request-ID: req-efaca269-2a83-4803-b2ea-006f91dce361)\u001b[0m\n\u001b[1;31mError: Execution of '/usr/bin/openstack project create --format shell services --enable --description Tenant for the openstack services' returned 1:
....