By default, Graphene redirects location requests to their own implementation as this is far more private. However, this implementation does not support network location, so you need GPS signal for that to work.
You can change this to use Google's implementation instead, as long as you are cool with Google tracking your location. The way to do this is outlined in the Configuration section of this page. Make sure that you have the sandboxed google play services installed as this uses those.