I have an insane amount of bookmarks. My menu is rather speedy. Check that
A) You arent overtaxing the system. Sounds stupid, but if your system is getting overloaded, this can easily be the case. Symptoms would be slow FF load times, other laggy apps, etc.
As you can see my load is a wee bit high, but thats only because I have a few daemons that are resource hungry and Transmission (BitTorrent) running, and a paused Totem video. Get over 6 and then its ugly real bad.
[andrew@andrew-desktop-fedora ~]$ cat /proc/loadavg
0.78 1.02 0.95 1/182 17093
Memory can be a shortage too,
As you can see here, I have alot of RAM still free even with the naughty apps that are sucking my resources, so I am definitely in great system shape.
[andrew@andrew-desktop-fedora ~]$ free
total used free shared buffers cached
Mem: 2071212 2018344 52868 0 17104 675276
-/+ buffers/cache: 1325964 745248
Swap: 4192956 374632 3818324
B)Fubar FF extensions. Clean out your firefox extensions to the default ones. I have found that Google Toolbar is evil. I use Google's Bookmark extension without any problems.
Check those in that order. I have found that always blaming FF isn't necessarily a fair thing, although it does end up being the case somewhat often.