We got this error for all of our packages. I procmon'ed it and it appeared to be OK, saying that it was creating folders and loading the .appv package, but when I went into the D:\AppVData\PackageInstallationRoot folder, nothing was in there.
It turns out that with Hotfix 4 Microsoft has changed the PackageInstallationRoot permissions to require Authenticated Users (Read/Write) to the folder, without this ACL we get the above error. Microsoft appears to have made this change to allow Globally published application to be able to be launched on network shares without requiring the local machine account added to the share. Unfortunately, without the ACL on the local folder we get the error above. To create the folder with the correct ACL's, just delete the existing folder and restart the AppVClient service. The service will auto-create the folder with the correct ACL's.
If the service does not recreate the folder, you may need to run the AppV publishing scheduled task to get it created.