Solution to "Invalid download URI."
After some time of troubleshooting this issue, and performing all the previously recommended steps, we believe we found a really easy solution. In fact, I feel really frustrated that I didn't do this to begin with, but hey, live and learn.
This solution will typically work for folks who are getting this on almost every app, with a few exceptions. You may notice that some apps will install while others throw this "Invalid download URI." When an app is downloaded, the installer will then look to see where the app wants to install. Most of the time, these apps request to use the "SD Card" mount point. On most Android devices, even if you do not have a SD card installed, you will still have a SD Card mount point, which simply points to another location within the phones storage. It turns out that in this case, the S4 we were working on, had a SD card installed, but it was defective. So the installer would attempt to perform the installation step, but since the SD card wasn't responding appropriately, we would get this "Invalid download URI" error. After the card was removed, the Play store began functioning normally and apps would install without any issues.
Hopefully this helps everyone who had no success with the cache clearing and permission change solutions.