Android: Getting Current Location

Android: Getting Current Location

In my code I request for location updates (NETWORK_PROVIDER) and then wait
for 5 minutes before requesting for the lastKnownLocation. About 50% times
I get a fix and onLocationChanged is called. But in some cases I am
getting the lastKnownLocation which is as old as 7-8 hours and in some
cases I do not get any lastKnownLocation at all.
My question is that when I am constantly connected to the network provider
and even after waiting for 5 minutes post requesting for a fresh location,
why am I not able to get a fix.
I have tried almost everything which has been suggested in different
questions on SO but hasn't helped me much.
Rather than calling the requestLocationUpdates(), is there anything else
which might help me getting the current location. I mean some other API
dealing with cellular network which might give a clue about the network
provider tower location.
I have been trying to optimize the performance of the location fetching
exercise in my code since many days but have not been able to get over
this problem. Please help.