With VS 2010, the IDE recreates the user's 10.0_Config registry hive and remerges menu resources when it detects a change under HKLM\Software\Microsoft\VisualStudio\10.0. For VS 2012, the IDE team felt this had too much of a negative effect on startup performance, and the feature was removed.
Consequently, if you deploy your VS Package(s) with a custom setup/installer, your installer must run devenv.exe /setup to ensure the registry changes you add under HKLM\Software\Microsoft\VisualStudio\11.0, are propagated to the users 11.0_Config hive.
The only exception to this is when you deploy your package via VSIX. Packages installed by the VSIXInstaller, do not have this requirement.
Therefore, if you find your package does not load under VS 2012, and running devenv.exe /setup fixes the problem; you are in good company. I have seen a number of partners (internal and external) that have encountered this problem.
There is mention that this is a requirement in the documentation link below, but in the absence of a "What's New/Changed" topic for the VS SDK, that can be very easy to overlook.