Did you manage to get the locations in deep sleep mode ?
Even I am facing the same issue.
I observed I received the locations (that were updated during deep sleep mode) after the device woke up but with current timestamp (time after wokeup).
I have made my Application class as Listener for my own reasons. And I am not pretty sure if the reason for onLocationChanged() not hit is if the component was not running in deep sleep mode..in my case it is Application.
I have ONE SOLTUION - you can have ALarmManager which fires at regular intervals and you acquir partial_wakelock that wakes the CPU up and call getLastKnownLocation() and release the wakelock. This does not seem to be a suitable solution for my case as I want locations based on Displacement.
EDIT
The working solution is http in deep sleep mode. Though question is irrelevant, context is same. Receiving locations this way should also work.