If you haven't already, go to create new key and choose 'Android'. Then under the allowed application bit enter 72:A5:F8:A0:...:YOUR.PACKAGE.NAME, with the first part the SHA1 got got above, and the package name the name in your AndroidManifest.xml file.
On that same page, it'll give you a API Key. Put that in your Android Manifest as under the Application tag showen:
You need to do this for each machine you build the application on, i.e. get the debug key, generate the fingerprint and tell Google about it on the above URL.