Can I create a github repository named the same as one that existed but was deleted?

You certainly should be able to create a new one with the same name. I'm fairly sure I've done this before.

I'd leave it for 5/10 minutes and try again if I were you.

I faced this dilemma. But then I noticed I can rename a repo and then create a new repo with the old name, and in case there is a problem creating one with the old name, just rename the old one again... So no need to delete the repo...