We experienced similar problems, further investiagtion showed that there we too many requests for the Geocoding API key used. To us it looked like everybody usng the APpStore widget is using the same Geocoding API key, because it is hardcoded in the code.
We filled a request to Menidx to allow a personal Google Geocoding API key to be used, in stead of a hardcoded API key owned by Mendix.
Mendix has then released an update which allows a constant to be set containing your personal Google Geocoding API key. Since that time we do not experience these problems any more (mind that you still limit the number of requests per second). So check if you are using the latest widget form the AppStore.
What sort of error do you get? If it works locally and not in the cloud it sounds like a java permissions issue.
Could you submit a stacktrace?