Hit CTRL+SHIFT+DEL, change the option to Everything and then checkmark Browsing History, Cache and Cookies. Then click "Clear Now".

Next, go to Tools | Options | Advanced and in the Network tab | Offline Storage, click the Clear Now button.

Close Firefox via File | Exit and then restart it again.

I can't see what plugins you have installed, but the most common ones that don't get updated are Java via Windows Control Panel | Java | Update Now, Flash via http://get.adobe.com/flashplayer/ and Shockwave For Director via http://get.adobe.com/shockwave/

I had this same problem.

It turned out that the problem was that my firewall was blocking incoming connections to firefox.exe from 127.0.0.1.

After i configured my firewall to allow such connections (I had to set firefox in my firewall to "allow all" since the firewall i 'm using doesn't allow detailed rules) the start-up time was reduced from 1 minute to a few seconds.

See [Connections established on startup]

In Firefox 4.0 you can configure the loopback address by checkmarking "Use system proxy settings" which is actually the default, in Tools | Options | Advanced | Network (tab), then click the Settings button.

I don't know of a firewall which doesn't allow you to configure it in different ways though. Which one is it if you don't mind me asking?

Tools > Clear Recent History > Everything /clear now

Made a significant difference in startup time...