I had a similar problem and found that polling the Geocoder until i got a result worked. Here is how i did it, so far works great.
try {
List<Address> geoResults = geocoder.getFromLocationName("<address goes here>", 1);
while (geoResults.size()==0) {
geoResults = geocoder.getFromLocationName("<address goes here>", 1);
}
if (geoResults.size()>0) {
Address addr = geoResults.get(0);
myLocation.setLatitude(addr.getLatitude());
myLocation.setLongitude(addr.getLongitude());
}
} catch (Exception e) {
System.out.print(e.getMessage());
}