UAC and SWV

Would it be fair to assume that your users are running with non-admin accounts?
If so, you need to adjust permissions on the fslrdr folder where the virtualised applications live, so that standard users have full read write access.
All modern windows operating systems restrict user access to read only over much of the hard disk, with only "user" areas having full permissions.
Virtualisation means that user content is actually being written not to the user profile, but to the writeable layer under the fslrdr folder. If the user has no write access there, then the update will give an access denied message, as virtualization does not modify basic permissions in any way. (If it did, then it would present a major security risk.)

With UAC enabled, no user is a full admin on the machine as UAC limits the access rights of the user. That is why running an installer, for example, causes the UAC to ask the user for permission to run the process with elevated privileges. Without this permission, the installer only has "user" rights.
Alternatively, you can right click on a shortcut in your start menus and choose "Run as Administrator" if you want the target application to run with admin privileges - if you don't do this then again your permissions are restricted.

So for example, if you start a CMD shortcut from your "admin" account with UAC enabled, and try running IPCONFIG /RELEASE - you should get an error message about having insufficient rights. However, if you right click on the CMD shortcut in your start menu and choose "run as admin" then IPCONFIG /RELEASE will work.

As far as giving rights to apps  - there is no simple one-stop solution that fits all requirements. Do you have any existing standards for applying user permissions in a non-virtualised world, or are all of your users running admin accounts?

If you turn off UAC, but still virtualize the applications, do they work correctly? (Not recommending this for actual use; just for testing.)

UAC really shouldn't be getting in the way if the changes are actually going to the profile, because the user actually DOES have the rights to go to the profile. UAC primarily messes with changes that are going to an area where the (non-elevated) user doesn't have rights to modify things.

Also, I'm noticing that the exception you posted actually says something about a FileNotFound exception, even though the summary message does say access denied. It would be useful to use a tool like Process Monitor (Procmon) to monitor the system as this error occurs, and see if there really is an access denied for the file, or if it's a file not found for some reason.

How are your applications configured when virtualized? (Do they use application isolation features, excludes, etc.?)