Rated 4 out of 5 stars
Some, but not all colored icons show up in the Bookmarks Sidebar for me. I use AIOS.This review is for a previous version of the add-on (0.4.14).
I know of three circumstances when this can happen:
1) Bookmark icons don't update until you next visit the page.
2) redirected pages don't have icons (bugs 389642/423127)
3) bookmarked fragments will not initially have an icon (bug 420605) until next visit.