This name conflict seems to happen when renaming a page that has child pages. There may be some faulty interaction with the cache going on.
Consider an example list of wiki pages with wiki3 being a child page to wiki2:
If I rename wiki1, wiki3, or wiki4 I am able to create a new page immediately with that same name. If I rename wiki2 to wiki2new, I can't create a new page named wiki2.
You should be able to fix this issue and create a page with a reused name using one of the three workarounds below:
1) recycle the site's app pool
2) (using names from above) edit wiki3 and re-enter wiki2new as the parent page. Even though the parent name shows correctly as wiki2new on the child page, the old title of wiki2 may still be in the cache as wiki3's parent page.
3) Wait for the cache for this wiki to expire
I will certainly log a bug about this and the team will take a look.