I am trying to write a Java application that, given a city and a radius, returns all the nearby cities. I thought the Google Maps API would be able to do this, but I am getting no luck with the Places API, it just returns points of interest (e.g. restaurants, ...). Is there a way of doing this with the google API or is there some other API (or way of doing this) that you would recommend?
You are likely correct that you will not want to use the Places API. You may want to see if there is a way to use geocoding/reverse geocoding to get what you want. See http://code.google.com/apis/maps/documentation/geocoding/.
Depending on your performance and accuracy requirements, you may not be able to easily do this (especially globally) with Google Maps API (or any other free tool), but you might be able to get something that sorta kinda mostly-works, especially if you have a geographical restriction (e.g., just the U.S.) that might simplify things.