So far, pretty easy and straightforward process. The store review process rejected the application. I asked the to run WACK locally (Windows Application Certification Kit) that is on any system that is doing Windows 8 development. To run it, simply hit the windows key on your keyboard and type cert, it should be in the results. It's also available at http://msdn.microsoft.com/en-us/windows/apps/bg127575.aspx
WACK failed and gave the following issues in the report. I'm including everything for those that find this via a search engine trying to solve their own issues. However the fix was quite simple. In Visual Studio ensure you are doing a RELEASE build. The problem here is when a Debug build is selected in Visual Studio, the debug version of the Unity libraries are referenced instead of the Release version. Debug libraries have optimizations removed and a bunch of diagnostic information included in them (for ex information to link in PDB files for debug information). Simply select "Release" in Visual Studio for build settings, recompile via the build menu or control-shift-b, which is also the same hotkey for build in Unity and voila!
Failing application details:
Error Found: The binary analyzer test detected the following errors:
File \AppX\BridgeInterface.dll has failed the WXCheck check.
File \AppX\BridgeInterface.dll has failed the SafeSEHCheck check.
File \AppX\Catch Falling Stuff.exe has failed the WXCheck check.
File \AppX\Catch Falling Stuff.exe has failed the SafeSEHCheck check.
File \AppX\UnityEngineDelegates.dll has failed the WXCheck check.
File \AppX\UnityEngineDelegates.dll has failed the SafeSEHCheck check.
Impact if not fixed: If the app doesn’t use the available Windows protections, it can increase the vulnerability of customer's computer to malware.
How to fix: Apply the required linker options - SAFESEH, DYNAMICBASE, NXCOMPAT, and APPCONTAINER - when you link the app. See links below for more information:
Fixing Binary Analyzer Errors
Error Found: The debug configuration test detected the following errors: ?The binary UnityPlayer.dll is built in debug mode.
The binary BridgeInterface.dll is built in debug mode.
The binary UnityEngineProxy.dll is built in debug mode.
The binary UnityEngineDelegates.dll is built in debug mode.
The binary Catch Falling Stuff.exe is built in debug mode.
This package has a dependency on Microsoft.VCLibs.110.00.Debug.
Impact if not fixed: Windows Store doesn’t allow a debug version of an app.
How to fix: Please make sure the app isn’t linking to any debug versions of a framework, and it is built with release configuration. If this is a managed app please make sure you have installed the correct version of .NET framework.