Yes a soft, new toothbrush will do fine. It wouldnt be a bad idea to do this regularly just to be safe. I lost mine due to a still unknown algea smoothering it, even though it was in a good flow area (fuzzy and fine like you mentioned, a dark red color, not cyno though). I learned that even with the right flow some algeas will still take hold anyways. Exceptions to the rules I guess........HTH.