I have notice that the map does not get updated when you get the "New habitable planet" survey event.
In fact, I used to completely overlook this previously when it occured.
However, I have noticed that if you save the game and then reload, the map tends to get updated with correct icons.
I have seen this happen several times where I would say - "I didn't realize I could colonize that planet" ???