Gallery2 and Google Maps - Works only for admin

I changed the domain for an existing Drupal 6 installation. Among many other modules, I have Gallery2 and Gmaps. The site displays map of images and nodes.
Previously, before the domain change, I used one Google Maps key for both GMaps and Gallery2 Google Maps, and all maps rendered fine through the embedded Gallery pages (I think).
When I switched the domain, I made all the necessary adjustments to the Gallery2 and Drupal configuration, and everything works fine now, with one exception - the Gallery2 embedded Google map only works when I am logged in. The anonymous user gets this:

The Google Maps API server rejected your request. This could be because the API key used on this site was registered for a different web site.

and then

You do not have a profile setup for this website to use the Google Map. Review your settings in the Admin Panel or check the Wiki.

I did change the profile for the Gallery2 GMap plugin, and the URL in the profile is http://baycolonyrailtrail.org. The key is the same as in the Drupal GMap configuration (and the Drupal GMaps work fine for anonymous users).

How is it possible that an authenticated user sees the map, while an anonymous user sees the Google error? I must have missed a configuration change, but I cannot explain this behavior.
Again, I am not 100% certain that the Gallery2 image map worked for anonymous users before I changed the domain. Regardless, I'd appreciate a hint where I could start looking.

http://baycolonyrailtrail.org