OK. Obviously not going to reinstall the application, not even close. Looking into the event logs I see absolutely nothing related to that. Looking into the installed applications and updates - nothing recently modified.
This thread at the Visual Studio forum suggests that this happens when you install Visual Studio 11, but our environment does not correspond to that scenario. We are running Visual Studio 10. However, since that was a production server and I needed to figure that out quickly, and this solution was posted by Microsoft, I've exported the registry key and deleted it as suggested in there:
1. Start regedit.exe
2. Go to HKEY_CURRENT_USER\Software\Microsoft\SQL Server Management Studio
3. Delete 11.0_Config
4. Restart ssms.exe
That helped. Just make sure you export the key before deleting it.