You may need to run the Gradual Site delete timer job in Central Admin. When a site is deleted from SharePoint users will lose the ability to access it but it isn't actually removed from the content database until that job has run. Depending
on how much content was in that site you may have to wait a while for the task to complete but once it does you should be able to restore without issue.
-Chopps