Make sure that "Loaction Services" is active. Also, make sure that you have set the permissions for Google Now (under settings) to allow it to use your location.
I once had a similar issue but restarting the phone fixed it... I did try something else and it fixed it, too... Try disabling Google Now (Google Search settings, there should be a switch there). Then restart.
Can Maps get a lock on your location? With and/or without GPS?