Is this on a real phone? Does the phone have a GPS? Is the GPS turned on?
One other point to look at is that you should be building your application against one of the Google API levels (this is done somewhere in the Project Properties in Eclipse). And when you are running an emulator make sure the AVD has the Google API, not just Android (you usually have the option to do Android API level 17 or Google API 17 for example. Make sure you use the Google one).
Yes, make sure your compile target uses Google API (of whatever is the appropriate API level for your app). The Geocoder uses some Google APIs in its implementation, so if you don't build against them they aren't available when running the app.