Just had this issue which was somewhat perplexing because normally when you get an error like this you tend to find there are missing tabs and maybe a missing site code. The location services log file was saying that there was no information being returned from the MP, yet as you can see from the image above everything looked otherwise intact.
When the client was installed, a Fallback Status Point was specified. A Fallback Status Point was installed on the primary site but it transpires that this isn’t enabled by default (at least it wasn’t in our case). Once this was enabled everything began working again:
(click image to enlarge)