I’m having the exact same issue. Is it possible to make the answer public?
Like Jeff, my API key has been added as described in the docs, and the maps display correctly in both the front and back end, but only when trying to add an address do I get the same error.
Thanks.