Just want to add my experience with the issue... i'm using a i9100 with miui 3.5.31, i have this problem too and no baidunetworklocation.apk on the phone... hope it will be fixed soon
Solved right now, i've downloaded the GAPPs from cyanogenmod site and installed the "NetworkLocation.APK" from the zip to the system/app folder... set permissions, reboot and it's done.
