I set up a new reporting server and had the same issue (this affects Power BI Report Server too) and managed to solve it based on the other answers above but as I had specified specific service accounts the fix did not work so this is what should work no matter which account is used as the service account for running the report server.
First on the server open Report Server Configuration Manager and click on Service Account on the left. Review which account is being used to run this.
Next go to Execution account and review which account is set up there as the execution account needs to read that registry key against the Service Account (this is not the generic "Service Account" in Windows).
Now go to Registry Editor still on the server to this key (can be copied and pasted on more recent Windows Server versions):
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\ProfileList
Click on each SID one by one and look at ProfileImagePath
to find the name of the service account so you know which SID it uses.
Now go to the following location:
Computer\HKEY_USERS\[Service Account User SID As Shown in Report Server Configuration Manager]\Software\Microsoft\Avalon.Graphics
Grant read access to the folder to the user set up against the execution account in Report Server Configuration Manager.
Now go back to Reporting Services Configuration Manager and stop and start the service and reports should now export to Excel.
Alternative workarounds as listed, to export to an older .xls format or remove the execution account work as then Avalon Graphics are not used but the option above would seen the better option unless an Execution Account is not needed. Running the service as an elevated user would also work but probably adds more risk.