I believe "VisualStudio.Launcher.sln" is ok. I have that on one of my machines as well and msbuildshellex is working without issues.
If you download the latest msbuildshellex source code and right-click on the "MSBuildShellExtension.sln" file from the trunk, it should display the MSBuild context menu.
Do you get the context menu if you right-click on "MSBuildShellExtension.sln"?
Do you and your colleague have the exact same sln file (no modifications)?
It works for me: Windows 7 Ultimate x64 SP1, Visual Studio 2008 Team System, Visual Studio 2010 Ultimate, MSBuildShellEx 64-bit (but Visual Studio is not a requirement).
Also, are there any relevant errors in the Windows Event Log?
I am also wondering if you can list any other programs you have installed? Are any programs another type of windows shell extension?
Maybe your anti-virus is blocking the shell extension for some reason, so you may want to disable it during installation and\or when you try to right-click on a sln file.
You can also download ShellExView (http://www.nirsoft.net/utils/shexview.html) to see if "PerformanceDude.MSBuildShellExtension.ContextMenu" is registered and enabled on your system.
If it still does not work, maybe we can setup a remote connection and I can help troubleshoot the issue.