getLastKnownLocation() uses the location(s) previously found by other applications. if no application has done this, then getLastKnownLocation() will return null.

One thing you can do to your code to have a better chance at getting as last known location- iterate over all of the enabled providers, not just the best provider. For example,

private Location getLastKnownLocation() {
    List<String> providers = mLocationManager.getProviders(true);
    Location bestLocation = null;
    for (String provider : providers) {
        Location l = mLocationManager.getLastKnownLocation(provider);
        ALog.d("last known location, provider: %s, location: %s", provider,
                l);

        if (l == null) {
            continue;
        }
        if (bestLocation == null
                || l.getAccuracy() < bestLocation.getAccuracy()) {
            ALog.d("found best last known location: %s", l);
            bestLocation = l;
        }
    }
    if (bestLocation == null) {
        return null;
    }
    return bestLocation;
}

If your app can't deal without having a location, and if there's no last known location, you will need to listen for location updates. You can take a look at this class for an example,

https://github.com/farble1670/autobright/blob/master/src/org/jtb/autobright/EventService.java

See the method onStartCommand(), where it checks if the network provider is enabled. If not, it uses last known location. If it is enabled, it registers to receive location updates.

There's nothing to fix, this is expected behavior. getLastLocation returns the last location IF THE SYSTEM KNOWS IT. It almost never knows it. So it will almost always return null. If you want to get an assured location, use requestLocationUpdates. But you can never rely on getLastLocation working, and even when it does the data may be old. It should really only be used in very limited circumstances.