Make a test and change the package name of both apps. Do they still behave differently?
The one with the problem continued to have the problem and the one that did ask for permission for background location tracking stopped doing so.
I did uninstall and reinstall the proglem package originally before I noticed the problem.
At the same time I started getting java.io.FileNotFoundException - EACCESS (Permission denied) problems on File.DirRootExternal even though I request and approve PERMISSION_WRITE_EXTERNAL_STORAGE (and read). I got this on the working app as well when I installed it with a different name.
Could this all be part of a bigger problem introduced with Google's new Play Store Policy - App content managment and approval system just gone live in the last few days and with a 30 day time limit to get all approvals sorted.
Could it affect the device and hinder the option on all newly installed apps unless its preapproved through Google Play. Something that is difficult to do since they demand a video of the function which is impossible if you can't make it appear on screen without the same approval. A chicken and egg what came first scenario.
agraham: The explanation on the link is a bit general and it doesn't specify what exactly would trigger the location "Allow all the time" option.