Тоже долго мучался с этой проблемой...
Ждал выхода новой версии... вышла 0.7, но когда поставил обнаружилось, что эта проблема с выделением цветом по категориям так и не решилась... расстроился...
НО! Потом полез колупатся (тестить, пробовать и т.д.) и наконец-то разобрался:
Весь прикол в том, что по умолчанию категории (в русской версии программы) введены, естественно, на руском языке, а если переименовать или ввести новую, но только латинскими буквами, сразу же Sunbird нормально выделяет тем цветом который Вы задали!!!
Обнаружил что в файле настроек (prefs.js) категории, содержащие кириллические символы (буквы) отображаются (сохраняются) не корректно!
Так что это скорее всего БАГ только русской версии!
Как выход из ситуации - создаю или переименовываю категории транслитом (т.е. Личное - Lichnoe).
Не удобно конечно, но будем надеятся, что разработчики этот баг исправят в новых версиях! :)