Try using all the location providers and see if it solves your problem, i.e. something like
LocationManager lm = (LocationManager) context.getSystemService(Context.LOCATION_SERVICE);
List<String> allproviders = lm.getAllProviders();
for(String provider : allproviders) {
myLocationManager.requestLocationUpdates(provider, 5000, 0, this);
}
If this code always works, then you'll just need to work out why your code is ignoring a provider that my code finds. Could easily be something to do with your power or accuracy criteia.