ну во первых посмотрите Система - Администрирование - Системный монитор на наличие сетевой активности при загрузке закладок. если трафик идет, значит нужно просто дождаться окончания загрузки.
а так, иногда при глюках помогает переустановка пакета.. синаптиком поставьте файрфокс на повторную установку.. ну и если нет никаких ценных настроек файрфокса, почистите папку ~/.mozilla и заново установите расширение

Странно.
Тоже пользуюсь google-toolbar на firefox под Ubuntu 7.10, и такое сообщение тоже видел, но только по одному разу - сразу после установки google-toolbar. При всех последующих обращениях к закладкам - все сразу отображается.
Банально конечно, но может просто дождаться стоит, пока закладки подгрузятся? Или все настолько плохо, что этот процесс не заканчивается? Тогда навскидку посоветовал бы для начала просто попробовать переустановить google-toolbar.