The permission you're looking for is in the Active Directory, not in the filesystem. Install the Windows Support Tools from the "\SUPPORT\TOOLS" directory on your operating system media to get ADSIEDIT installed.
Once you've got ADSIEDIT installed fire it up (w/ Start / Run / ADSIEDIT.MSC) and navigate to the "Domain", your domain's name, "System", "Policies", the GUID for the GPO where the errant software assignment is located, "Machine", "Class Store", and "Packages". There you'll find GUIDs for each package assigned in the GPO. You can use the "PackageName" attribute in the properties of each object there to locate the one that corresponds to your package with the errant permission. Once you find it, go to the "Security" tab and view the permissions. Using the "Advanced" view it's a snap to find the "not inherited" permission that corresponds to your "Authenticated Users" denial permission (probably listed as "Special"-- you can drill into the permission to see what is being denied). Remove the errant permission and you'll find that you can see the assignment in the Group Policy Editor again.