This is an expected behavior since even if the GPO was deleted, it still exist on the GPOADmin configuration store.
In order to create a new GPO with the same name of a previously deleted GPO, the following need to be done:
- On the GPOADmin console, expand the Search folders and select Deleted Objects
- Look for the GPO with the same name that was deleted previously
- Right click over the deleted GPO and select "Unregister and remove History"
This will allow the deleted GPO to be remove from the configuration store and allow to create the new GPO with the same name.