This is what worked for me in XCode 7.3
I have no idea how this worked since I didn't download a new provisioning profile which included the newly added device, neither did I touch anything in XCode after adding the new device. That's Apple magic for you.
I will try to add an explanation to this if I find one.