So, I used procmon to see what Firefox was doing when it was taking 60 seconds to start up, and it was reading a lot of files from a lot of different locations. The one that caught my eye was C:\Documents and Settings\me\Local Settings\Temporary Internet Files, and a quick check revealed I had over 7000 files in there. Not from Firefox, but from programmes which use the IE engine to display web pages and html content (like, XFire). I removed them all, and the startup times for Firefox dropped to about 15-20 seconds.
Then a friend sent me this link from LifeHacker.
So, not only do I now know what is causing the slowdown, I know why, and I know it’s classed as a bug.