An App ID with Identifier '' is not available. Please enter a different string

update

As of Xcode 8, iOS Team Provision Profile Managed by Xcode are now updated by Xcode automatically and correctly. They are not even listed at the Developer Portal, but generated on-the-flight.

However, the solution proposed below will still work. I've switched to using the automatic provisioning profiles.

tl;dr

Remove INVALID iOS Team Provision Profile Managed by Xcode from Developer Portal and manually create iOS Developer Provision Profile. Download it via Xcode and you should be good to go.

details

Problem:

I started to experience this after Xcode 7.3 (7D175).

What I did before the issue:

renewed Certificates (developer & distribution) via Xcode, b/c of their expiration;
installed two required certificates (developer & distribution) in my keychain;
re-generated Ad Hoc and App Store Provision profiles at Developer portal with new distribution certificate;
downloaded locally Ad Hoc and App Store Provision profiles via Xcode;
walk the project through the process of Setting up Xcode to automatically manage your provisioning profiles
noticed iOS Team Provision Profile Managed by Xcode was INVALID
saw Xcode being not able to Build & Run due to INVALID iOS Team Profile.

Tapping "Fix Issue" (~~the only way, I know to make provision profiles managed by Xcode valid~~), given the error An App ID with Identifier '<app id>' is not available.

Solution:

I have:

manually removed INVALID iOS Team Provision Profile Managed by Xcode from Developer Portal
manually created iOS Developer Provision profile
Downloaded it via Xcode

Now, I am able to Build & Run app to my devices.

TL;DR Xcode is very particular about the name you give your App ID in the member center. Having the correct bundle identifier is not enough. You must use the specific format shown below for Xcode to "see" your App ID.

Update: According to @isaacselement in the comments below, this issue has been resolved in Xcode 7.3.1.

@romrom's solution of deleting the App ID and having Xcode create a new one was a clue. Unfortunately it was a nonstarter for me since my App ID was used by a Store app and therefore could not be deleted.

However, I discovered through some experimentation that I could solve the problem by manually editing the exiting App ID. It turns out that Xcode is really picky about the name of the ID, and not just the bundle ID.

For a typical bundle ID such as com.mycompany.appname, the App ID name must be in this format:

XC com mycompany appname

a name in any other format won't be seen by Xcode.

How to check if you're affected / How to Fix

Log in to the Member Center.
Click on "Certificates, Identifiers & Profiles".
One the left-hand navigation bar, click on "App IDs".
Locate the App ID with your bundle identifier.
If that App ID doesn't have the correct name format (as shown above), click on it then click the Edit button.
Change the name and click Done.
Enjoy the reduction in stress and anger.

P.S. There are some related problems if you're using Xcode 7.3 in which it won't automatically create proper distribution profiles for you, even if you fix the name as I mentioned above. The solution is to downgrade to 7.2.1 or 7.3 Beta or use a tool like fastlane/sigh.

I had the same issue and solved by following steps below:

Go to Xcode Preferences > Accounts > Choose your Apple ID account
Tap on View Details
Tap on Download all and then Done

However it was working fine earlier but I don't know the reason why it stopped suddenly. I have gone through the steps above and found it working properly.