Try the methods in the cannot uninstall an add-on article. There is further information that can help here - Uninstalling add-ons - MozillaZine Knowledge Base

None of those worked for me. Is the only option left making a new profile?

Same here. Trying to uninstall 2 add-ons: Open in IE, and IE Tab Plus.

I tried various combinations of uninstall/restart/reinstall/disable, etc., and I tried everything listed above, but the 2 add-ons are still displayed as "This add-on will be uninstalled when Firefox is restarted."

Firefox 3.6.10, Win7 Pro 64.

You can delete the files extensions.* (extensions.rdf, extensions.cache, extensions.ini, extensions.sqlite) and compatibility.ini in the Firefox profile folder to reset the extensions registry. New files will be created when required.
See "Corrupt extension files": http://kb.mozillazine.org/Unable_to_install_themes_or_extensions
If you see disabled extensions that are not compatible on the next start in "Tools > Add-ons > Extensions" then click the "Find Updates" button to do a compatibility check.

You may also need to "Reset all user preferences to Firefox defaults" on the Safe mode start window.

Deleting the files (extensions.rdf, extensions.cache, extensions.ini, and compatibility.ini ) did the trick.

Thank you VERY much for your help.