10
This issue is a lot older than Visual Studio 2010. It goes back to 2005 at least. Lucky you, I was missing the New Class template once.
According to a bunch of sources, this trick works: If you are missing a template that comes with your installation, run devenv.exe with the /installvstemplates switch.
You'll need to exit out of all Visual Studio instances for this to work.
The trick is mentioned in the MSDN documentation: http://msdn.microsoft.com/en-us/library/0fyc0azh.aspx
Thread on the issue in a previous version of Visual Studio: http://social.msdn.microsoft.com/forums/en-US/vssetup/thread/8a5ae9e3-be7b-493d-831c-1e49e8103f26/
I wound up uninstalling and reinstalling my Visual Studio entirely but this trick probably would have fixed my problem.