I encountered it on Windows 8.1 Pro 64 bit, but the following observations may apply to other versions as well. It seems to be quite common issue, but I wasn't able to find any resolution for it on the Internet not counting disabling of the IE Protected Mode (PM) or creation of new user profile. Disabling of the PM is not good way to go, because it needlessly increases number of potential attack vectors. Creation of new user profile is easy fix for single user, but pain in case there are dozens user accounts facing this issue. That's why I dug deeper into it.
I quickly realised that this problem is mostly faced by users whose profile have been moved/copied to different drive. At first I compared registry dumps for user not facing the problem (let's call her/him "good user") and user facing the problem (let's call her/him "bad user"). Initially I thought that this obviously over-engineered PM feature stores drives UUIDs in registry hives, but the comparison of registry hives didn't reveal anything supporting this assumption.
Next I moved to Process Monitor to observe what's going there. I noticed a lot of "access denied" return codes from the CreateFile calls, all of them ending somewhere in the PM InetCache under %LOCALAPPDATA%\Packages\windows_ie_ac_001\AC. This also caused a bit delay when the download was initiated. Then after some delay, the Internet Explorer showed dialog box that it cannot download the file. If "retry" button was clicked, it used some different, probably backup directory and the file was saved with _exe suffix instead of .exe.
I checked ACL of the InetCache path, but it seemed OK. Even so I tried to give full access to everyone for this directory and sub-directories (it is generally not good idea, but I wonder what will happen). But it didn't help. Really strange, so I tried comparing ACLs of "good user" with "bad user". It revealed that there is SID of otherwise non-existent user S-1-15-2-1430448594-2639229838-973813799-439329657-1197984847-4069167804-1277922394 with full access rights on the path. I always enjoy such hacks :). I used the following command to fix the problem (I ran it multiple times with %LOCALAPPDATA% replaced by the user LOCALAPPDATA path, e.g. C:\users\user1\AppData\Local):
icacls %LOCALAPPDATA%\Packages\windows_ie_ac_001\AC /grant "*S-1-15-2-1430448594-2639229838-973813799-439329657-1197984847-4069167804-1277922394":(OI)(CI)F /c
Unfortunately there still persisted some user accounts that weren't fixed by this command. I rechecked one such account with the Process Monitor and it revealed that Internet Explorer created its InetCache on virtualised path which broke the PM. It seems that for correct PM function it's not enough if Users group or the group user is member of have full access to user profile, but it requires the user to be explicitly listed on the ACL of the profile directory and it's subdirectories. So I finally used the following command to fix the rest of affected user accounts (again ran multiple times):
icacls %USERPROFILE% /grant %USERNAME%:(OI)(CI)F /c /t
Later I realized that in my case the problem was probably caused by relocation script used for moving of user profiles. This script called robocopy command without the /copyall parameter. But there can be probably more sources of this problem (e.g. filesystem / ACL corruption caused by machine crash or installation of buggy drivers/SW, etc.).