New Google Play store version 4.1.10 fixes this issue.
Download: Latest Google Play Store 4.1.10 With Location Bug Fixes
This fixed it for me as well. I'm on an HTC One S. I downloaded the updated version of the play store on my phone by going to this site: Download: Latest Google Play Store 4.1.10 With Location Bug Fixes
Downloaded, ran it, then restarted my phone and now Google Now is picking up my location.