You may also want to "vacuum" the database Firefox uses to store your history - believe it or not, it greatly improves the speed of the awesome bar.
There are two ways to do this - manually, or through an extension.
Open the Error Console - Tools->Error Console (on a Windows computer, you can press Ctrl + Shift + J)
In the Code box, paste the following line (it's one line):
Press the Evaluate button. Firefox will seem to "hang" as it cleans up the database.
- You're done!
Extension: Vacuum Places - after it's installed, just click on the little vacuum in the status bar, and it cleans everything up!