So in my case this is very odd. I have 2 individual iTC accounts (don't ask why), anyway my old account had this name as an App and then it expired with the name still taken by that dormant account.
Now on my new account, I am trying to use that name so I had to go through the process of calling Apple Developer Support and finally I regained access to that old account and deleted the app completely that had the name.
So now I have waited over 48 Hours and on the current account I am using, I am trying to use that app name since like I said, it is deleted. But the thing is, it still says 'App name has already been used'.
I am very confused about why. This app was never in the App Store, just in testing stages but I fully deleted the app on the old account. Does anyone have any idea why the name is still taken?
If you created an entry for the first App in iTunesConnect, even if it was never submitted or uploaded, then that name is locked to that iTunesConnect App permanently.
From the Apple App Store Submission Tips
More good info here iTunesConnect_DeveloperGuide.pdf.
All the dev forums/docs I can find say the same thing, if you have ever used that App Name before, then that name is locked permanently.