Haven't heard of this issue specifically related to the Garmin Connect app. However, google returns several pages of issues/fixes related to "item not found" and google play. Are you able to install other apps?
What version of Android is on the device? It's got to be 4.3 or greater. GCM also needs 4.0 or greater Bluetooth HW (at least to sync, but maybe to install too)Thanks Jim - OS is 5.1.1. I'm unsure about Bluetooth version but I presume that shouldn't affect download.