At least we are eliminating possible issues!
I wouldn't worry about creating the macro at this point.
The next thing to check is on the Tools menu option in Excel. Select Add-Ins and see what add-ins are installed. You can uncheck any add-ins to see if they are causing the problem. If more than one add-in is checked, you can turn them off one at a time to test. It is likely a good idea to exit and restart excel after each add-in unchecked.
For example there is an add-in called Essbase that is known to take over your right mouse click and has been known to cause your problem.
If you do have the Essbase add-in, try unchecking that one first. If this solves your problem and you want to still use the Essbase add-in you can regain control of your right mouse menu in Excel by:
Re-check the Essbase Add-in under Tools->Add-ins
Go to the Essbase menu and select Options....
Click on the global tab
Uncheck the "enable secondary button" under the "mouse actions" section
One other idea... Are you using a Wireless keyboard and mouse? If so, do they have separate receivers or do they use the same USB Receiver?
Let me know how you make out.