I received this message after upgrading to Firefox 2.0.0.6: "this add-on will be upgraded when firefox is restarted" for almost all of my add-ons (ietab, bugmenot, firebug, delicious, tabmixplus, etc).
Solution? Delete this file and restart Firefox.
C:\Documents and Settings\{username}\Application Data\Mozilla\Firefox\Profiles\{profile_salt}\extensions.cache
or, for Vista:
C:\Users\{username}\AppData\Roaming\Mozilla\ Firefox\Profiles\{profile_salt}\extensions.cache