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.
Manually:
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):
Components.classes["@mozilla.org/browser/nav-history-service;1"].getService(Components.interfaces.nsPIPlacesDatabase).DBConnection.executeSimpleSQL("VACUUM");
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!