Try clearing your history cache. (Here's how: Tools/Options/Privacy/Clear Now.)

Then check your options. Mine was set at "Keep my history for at least *90* days." I changed it to 5 days.

Firefox worked fine for me at first and gradually got slower. I eventually figured it was because I had an enormous cache. Firefox has to load this cache into memory each time you start Firefox. Then it has to update it with a new URL each time you view a new page. Then, for each link on the new page, it has to scan its own list to find matching URLs, so it knows whether to display the link in blue or pink. I guess this can take a long time.

Let me know if this works.