|The 98 fix for that should be here:|
Scroll down to 'Restore New Command' and click on it. (In the description there's a 'Win-XP safe' link which apparently means if you run the fix on an XP machine it won't damage anything but also may not fix it.)
Extract the file and follow the instructions to install it.
That missing NEW option on the desktop is associated with Internet Explorer so it's possible the Opera install is what caused the problem in the first place. If the fix doesn't work you may need to uninstall Opera and go with something else.
It's also possible to restore a registry from before the problem started but that would leave Opera non-functional since it wouldn't be in the registry and reinstalling it may just cause the problem again. So don't try that--at least not yet. Let's see how the fix works.