I have spent hours on this over two days. I have tried everything listed about. I made an appointment with the Genius Bar. A few hours before my appointment, I decided to call Apple Care - Technical Support. FINALLY FIXED!
iPhone on iOS 9.1, Watch on OS2. Tried various forms of iCloud backup (OTA), iTunes Backup (Cable), iCloud Backup (via iTunes and a cable). The ONLY method where I was able to get Activity Data to sync was by completely wiping the phone, setting it up as new, and doing the same with the Watch.
So here was my dilemma. I have a TON of apps and a specific organization of the apps/folders, photos, etc. The WHOLE reason why we use an iCloud Restore or and iTunes Restore right?? To get the phone back to the state of which we have it perfectly set. I know that the Genius Bar was going to recommend to start over, setup as new. I wasn't having this.
Here is what I concluded to: 1.) The Activity App was corrupt in a sense that it was working fine, but was just not synching nicely.
After speaking with Apple Care, here is what they suggested. They said that it was possible that the OS was corrupt, specifically, the Activity App. Instructions were... 1.) Backup iPhone via iTunes and using a Lightning Cable. 2.) Put phone in recovery mode. 3.) Update and Restore iPhone to latest OS (at this time is 9.1). 4.) When phone restore is complete, select "Restore from iTunes Backup" and select the backup you just created. 5.) Pair Apple Watch.
Open Activity App -> VOILA!! Data is synching!!
Phone has a clean install of iOS 9.1 WITH all my apps, layout, text messages, and everything else that comes with a restore... except a CLEAN iOS Install.
Hope this helps!