SP2013: Restore Content DB Fails with full DB or max site collections but that is not true

Ok, this is a bug.

We are running SP2013 with the March 2013 PU.

Error:
restore-spsite : The operation that you are attempting to perform cannot be completed successfully. No content databases in the web application were available to store your site collection. The existing content databases may have reached the maximum number of site collections, or be set to read-only, or be offline, or may already contain a copy of this site collection. Create another content database for the Web application and then try the operation again.

The Content DB has got space and not in read-only

Looks like this is a bug.
By the looks of it after you delete a site it goes "somewhere" and you need to run the "Gradual Site Delete" Job.

This did not work for me.

Next, delete the site via PowerShell
Run: Get-SPDeleteSite

Get your Side ID
Run: Remove-SPDeletedSite -Identity {SiteID}

Remove the site's you need to remove. Nope Still not, this seemed to have worked for most people.
Went back i ran the  "Gradual Site Delete" job again.

Start the restore again and it worked.