It is possible you are being destabilized by a larger Empire.
My experience has been, should you be outnumbered (population-wise) 2+:1, propaganda and resistance will have limited effect. The affected planets will go into rebellion no matter what.
Also, the symbols may be appearing after the planet has failed its loyalty check (i.e., it's already lost the first roll). This is an important distinction, since newly founded colonies will immediately show their dissatisfaction before you end the turn. However, destabilized worlds may appear the turn after. Thus, you have only the current move to do anything about it. (Planets leave after 2 failed loyalty checks - any propaganda, etc. will not have a chance to kick in before the computer resolves the matter. However, Icannot speak conclusively, and am only swagging here.)
For this reason,. I dispense with propaganda, etc. on an already-founded/developed world which is unhappy. Instead, I keep 2-3 combat TR's as a fire-brigade in my Empire.
~SDC~