I found this question when I was moving from a development environment to a production one on an application that I am working on. This process involved the creation of a new profile, a new app ID, etc. I created the app ID and a profile, but the Team Agent had to configure the push notifications. I ran into the problem of “no valid ‘aps-environment’ entitlement string found for application” when I tried to resume testing with the new profile (after the app had been configured for push notifications). I then remembered reading a little caveat in the documentation:
“You have to modify the profile in some way (for example, toggle an option) for the portal to generate a new provisioning profile. If the profile isn’t so “dirtied”, you’re given the profile without the push entitlements.”
Source: Local and Push Notification Programming Guide
For me, “dirtying” the provisioning profile and reinstalling it was all that was needed to fix the issue. Per the documentation, this was required because the provisioning profile was created before the app was configured for push notifications. This may or may not help anyone, but this probably explains (and eliminates) the need to manually add anything to the provisioning profile.