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.