Hello Everyone
I had this problem since updated to Watch OS 2.0 GM (before public release). I contacted Apple, the haven't heard of the situation, they assigned to me an Engineer who has been in contacto with me every couple days to tell me to try things, none of them worked. Then found this forum, sent the link to apple to acknowledge them that I'm not the only one with the situation. I tried everything that everyone posted in here (par, unpair, restored both devices, set them as new) with the same result: third party apps with OS 2 native support aren't loading.
I guess it was a Watch OS Problem, but is not as couple of people reported in the latest posts. I got another phone borrowed that has never had an apple watch linked before. I reseted my watch and linked to the other phone as new and tried downloading native watch apps to the new phone and it worked!!, reseted the watch again and paired with my phone as new but the apps doesn't worked, so is not an OS problem, something is broken in the relationship with the Watch and the Phone. So, these steps worked for me:
1. Reset the Watch from the Watch settings App.
2. First reset All Settings on the iPhone from the settings App (tried without this step before and didn't worked)
3. Once the iPhone restarted, then Erase All Content and Settings
4. Configure the iPhone as a new device
5. Pair the Watch as a new device
6. Try to download a third party App with Watch OS 2 native support (like iTranslate) and the app loaded for me, as well the other apps
I tried wipe my iPhone again and restored from iTunes backup but didn't worked, the apps stucked on loading again, so I have to do all these steps again and set both devices as new. I lost all my activity and health data, as well all the data of my other apps; I didn't wanted this, but it's the price to pay to finally get my apps working in the watch again.
I hope this can Help.