Hi,
we had a similar problem, and the option "tlbimp" worked on all computers.
My (imperfect) understanding is: .NET uses wrapper assemblies to access COM components. If you specify "primary", you use an existing, pre-generated "primary interop assembly". According to http://msdn.microsoft.com/en-us/library/hfac4fky.aspx, "primary interop assemblies are provided by the same publisher as the type library they describe". If using "primary" does not work for you, this assembly does not exist on your computer.
The default is "tlbimp" and (from what I gathered) should normally work. If it does not work on your coworker's machine, the error message would be helpful. Errors were reported for VS2003 (search for the KB article "You receive an error message when you add a reference to a COM object in Visual Studio .NET after you install Windows XP Service Pack 2"), but I do not know if this applies to current versions of VS.
If you cannot make this work, I would suggest that you could read more about "Primary Interop Assemblies" and try to find where the primary interop assembly for Excel is located on your coworker's machine, then copy it to the machines of all developers.
Hope this helps.