LocationManager is buggy on many phones, since it depends heavily on the customized android open source code for specific hardware. Samsung phones are very buggy when it comes to LocationManager.
You should not use requestLocationUpdates, instead use getLastKnownLocation with a small hack. Just before the getLastKnownLocation call put the following hack and you should be able to use a AlarmManager to get regular updates.
HomeScreen.getLocationManager().requestLocationUpdates(
LocationManager.NETWORK_PROVIDER, 0, 0, new LocationListener() {
@Override
public void onStatusChanged(String provider, int status, Bundle extras) {
}
@Override
public void onProviderEnabled(String provider) {
}
@Override
public void onProviderDisabled(String provider) {
}
@Override
public void onLocationChanged(final Location location) {
}
});
LocationClient is the other alternative to LocationManager. It is more accurate, uses a hello a lot less battery.