I have Win 7 Ultimate, and this happened to me also.......drove me crazy for several months until I figured out what was causing it.
In my case, and most likely other cases, the shell extensions were at fault; specifically a third party extension by Systran.
To diagnose and fix this, I used NirSoft's shexview (
http://www.nirsoft.net/utils/shexview.html) to isolate and disable the offending shell extension.
I ran shexview and disabled all non-Microsoft shell extensions, which made the context menu work again, at last (YEAH).
I then added them back one at a time, and after logging off or restarting, I checked if the context menu was still working.
It took a while, but I finally found the shell extension that was causing the problem, and I left it set to disabled.
I hope this information is helpful, it worked for me, and I tried everything possible before this!
P.S. Just remember to log off or restart before checking if the shell extension that you just disabled or enabled has any effect.