Something went strange on my Mint 8 laptop (Mint is based on Ubuntu). Both in maximized and unmaximized modes, Firefox UI overflows the window. This results in an invisible horizontal scroll bar and the add-on icons disappear!
I tried all the solutions that were posted with no luck. My Firefox window was still too large. Turns out, it was due to a toolbar that I just installed (uh). Removing the toolbar brought the Firefox window back to normal.
If you installed a new toolbar and your Firefox window is too big, try disabling the toolbar and see if that helps.