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).