Turn off "Mock Locations"
I had the same problem with CyanogenMod 4.4.2 on a Nook HD+.
Google (a couple of hits) said you must turn off "Allow mock locations" in Settings>Developer Options, which I couldn't find.
Google then said "in Settings, go to About Tablet (or About This Device or whatever) and tap on "Build Number" repeatedly." After about 10 touches, "Developer Options" was enabled (it showed up in the Settings left hand column), and I could turn off "Allow mock locations". At Bat began working.
Damn, it's so obvious. Why didn't I think of that?