Hello Sense, correct, I always allow the apps access.I belive this could be an issue with the security settings of the Fire Stick .. When you first installed the app did you see the promt asking to allow access to storage ?
Also, I can confirm that the issue is as I mentioned above since I moved the file from the Downloads folder to the folder the app Downloader uses and then installed the update from within the Downloader app and it installed fine over the existing app.
I'm certain if you redirect the download location of the update file from Downloads to any other folder it will work 100%. I'd be more than happy to test.