This Pretty Link Slug is already taken – but it’s not

Hi there,

I had a page on my site that I deleted and need to set up a pretty link for the original page’s address to go to a new page
e.g mysite.com.au/oldpage (deleted)
now want to create a pretty link mysite.com.au/oldpage to point to mysite.com.au/new page.

I’ve ‘trashed’ the page and also emptied it from my trash
I’ve checked and when I enter mysite.com.au/oldpage the page is a 404 error page
But when I try and set up the pretty link it keeps telling me:

ERROR: This Pretty Link Slug is already taken. Check to make sure it isn’t being used by another pretty link, post, page, category or tag slug. If none of these are true then check to see that this slug isn’t the name of a file in the root folder of your wordpress install.

I’ve also trimmed my old clicks
I’ve reset my permalinks / htaccess
I’ve logged out and logged back in
I’ve cleared my cache
I’ve also searched my database and files and there are no images, files or even database results for “oldpage”… nothing I seem to do will let this pretty link be created.

Does anyone have any ideas?

What else is really frustrating is I’m sure something similiar happened to me a about year ago and then there was something I did and it got it working again – I just can’t remember what!