I take it you're not using Windows XP, because the Windows 95/98/ME Start {button} > Programs list became Start {button} > All Programs in XP. It would have been nice to have known which Windows you are using, as requested in the red note above the text window when you are composing a post.
You've had other suggestions here so I don't want to waste your time with something that was just a "try it and see" if any of the other suggestions work. But just in case they don't.............
There's a common theme to your problem. It's the error message that Firefox is still running. This happens sometimes with Windows, (all versions), when a program/application doesn't shut down properly, and this is a fault. However, it may not be a fault with Firefox. When installing Firefox you are given the option to let Firefox start when you switch on the computer. It is supposed to be a "quick launch" attribute where some of Firefox loads into memory at startup, so that when you need Firefox to surf the internet you double click the icon on the Desktop and Firefox loads up quicker. Most people, (that I know), disables this option on installing Firefox because it means starting Windows takes longer.
So, if you have a Firefox icon in your System tray, (near the clock), right click it and disable/closedown/exit it, I'm not sure which. Now try the upgrade.
If you do not have a Firefox icon in the System Tray, is there one whenever you startup the computer? if so, restart the computer then close that icon down. If not, goto the next step.
Next step, 
Not having an icon in the System Tray does not mean Firefox is not still running in the background in error. Sorry, too many negatives there. What I mean is, even if there is no icon in the System Tray, it could be that Firefox did not shut down properly and Windows thinks it is still running.
So, to test this, press the 3 keys CTRL+ALT+Del together.
In Windows 95/98/ME this brings up the "Program Manager" which lists all applications running. If Firefox is listed, highlight it, and close the application down.
In Windows XP, this brings up the "Task Manager" which has tabs that list any applications running and all Processes running. Under the Applications tab, check to see if Firefox is running, and click End Task. Then under the Processes tab, check to see if there is an entry for Firefox.exe. If so, highlight it and click End Process.
Now try the upgrade again.
If all that fails, please would you double check your Firefox, (or Mozilla Firefox), folder in Start > Programs. I am sure there should be at least two shortcuts there, one for Mozilla Firefox, and one for Mozilla Firefox (Safe Mode). If not, don't bother checking elsewhere.
Instead, make a copy of the Mozilla Firefox shortcut from the main icon on your Desktop by right clicking it and selecting "Create Shortcut". A new shortcut will be created called Mozilla Firefox(2). Right click that shortcut and select Properties. In the box that says "Target" type, (or copy and paste), this in;
"C:\Program Files\Mozilla Firefox\firefox.exe" -safe-mode
Make sure to include the whole line, including the quotation marks.
If your Firefox is located other than in C\Program files, change that as appropriate.
Now click Apply, then OK. The double click that shortcut to start Firefox in Safe Mode. Try the upgrade from there.
Once you've finished with that shortcut, you can delete it. Make sure you delete the right one.
Good luck.
Mark