The different version numbers you see as the firmware versions differ based on what device you have (a va is different than a va-hr, which is different than a fenix 3, etc.)
Check out this thread, as there are things you can try:
See the thread I linked to in the post right before yours. The app store may not know you'd updated your FW (as often happens with a new watch right after you've set it up), and there are things there to try.
Hi there I had this problem with my recently purchased (yesterday) Fenix 3 HR.
I had paired it with my phone first. This appeared to create the first record of software version on online Garmin Connect for my Fenix 3 HR. Which was whatever software came on the device at manufacture.
Then I connected it to Garmin Express (computer hookup with USB) so I could get the latest software, which was successful, but upon attempting to download a watch face the message came up that I needed to update my software. I gave up.
Later today after reading these posts I unpaired my device with my phone and re-paired it. This must have triggered the software check to confirm or overwrite the software record in online Garmin Connect.
I was able to successfully download a watch face after this. I imagine anything that will cause this software check trigger should work, as mentioned above.
^ This. :) There can be some delay between when firmware is updated on the device and the device status percolates through to GCM if you're using both GCM and GE to perform updates and install apps. For those still experiencing this problem, I recommend that you first connect your device to a computer and check for firmware updates with Garmin Express. Once the firmware is installed, disconnect the device and allow the firmware to fully update. Then reconnect the device and try installing an app through Express--this should work.
3 years later and this still can happen, I did this to a T when I just got my vivoactive 3, re pairing the device to my phone and now everything works great! Thanks for this!!!