Start the process of submitting an application with iTunes Connect, fill in the name of your new application, but don’t complete the submission.  As long as you enter the name and fill in all the relevant fields with any sort of data you can try to claim the given name. The key is the “Upload binary later” field.

You should then see if someone else has this same store name and if not then you can claim that name.

If the ideal name is gone then consider that you can have a different name in the store than is displayed on the iPhone and therefore you might be able to use a permutation on the name for your store submission and your desired name within the application itself.

How To

Go to iTunes Connect within the online iOS developers area > Manage Your Applications > Add New Application

You need to create a bundle ID for the app which you can do on this page first