Yes if you wanted links you have clicked on to change colors then you need to have it in your history. So go to your history and set the days you want want to keep a history.
I would also check any other programs that can also clear your history because even if your not clearing it from Firefox you may be clearing it from another program.
I use Zone Alarm and it would have the option to clear on netscape but it will not clear anything on firefox. I have a older version of ZA Pro but I still don't think they have added Firefox from what I hear.