I have a Note 3 and have the same problem. I have reset both my phone and the Gear to factory defaults and have no luck. Fitness with Gear will synchronize fine, but I cannot install any apps.
Sent from my SM-N900V using Tapatalk
Samsung Galaxy Note III
Apple iPad 2
Samsung Galaxy Note 8.0
Archos 70 (250gb)