That error typically means that the plugin couldn’t connect to Google’s Maps API to geocode the input you entered, and doesn’t necessarily mean there’s anything wrong with the plugin. There could be issues with your network or server that are interfering, or Google could be blocking requests from your netblock due to abuse, etc.
If you read the FAQ and review the relevant support forum posts you’ll find more information.
If you want to try and fix the problem, please follow the instructions in the FAQ and reply with all the relevant details.
In addition to the regular info, please also send me samples of the input you’ve tried and the name of your hosting provider. If you get any extra details in the error message, submit those too.
If you’d like a workaround in the mean time, you can use longitude/latitude coordinates instead of an address. See the FAQ for details.