I was eventually able to solve this with a combination of methods.
First, I had to take ownership of an modify the permissions for the following node:
HKEY_CURRENT_USER\Software\Classes\Local Settings\Software\Microsoft\Windows\CurrentVersion\AppModel\Repository\Packages
I used the method detailed here:
http://www.kapilarya.com/fix-error-ms-windows-storepurgecaches-while-resetting-app-cache
Then, after running the WSReset command, I was able to get the store working. However, none of my apps worked.
To get my apps working, I had to uninstall and reinstall EVERY. SINGLE. STORE. APP. This includes the standard Microsoft ones like Weather, Mail, etc. The only exception is the modern version of IE, which still doesn't work. :(
Now, everything seems to work fine.
Quick note: While I am not sure what triggered this, I do have a suspect. I believe this happened after I changed the password for my Microsoft account. I'm not willing to do that again to try and recreate the behavior though.