Another cause of gum bleeding can be Lichen Planus. It can vary from not noticeable, to irritating, to painful and bleeding throughout the mouth. Oral Lichen Planus is just one symptom of what can be body-wide involvement, again quite variable in type and degree. If diagnosed with oral Lichen Planus, first switch to a tooth paste without sodium laurel sulfate, like pronamel or parodontax.