Dear Christopher, first I have to say I am not deeply familiar with the technique. As far as I know the efficiency of plasma cleaning depends also on the gas chemistry you use. To get rid of the carbon residue you need some oxidizing mixture - one of the common ones being Ar+O2 (3:1 v/v). Since you have not described the process you used, it may be the case that plasma based on air (like when you use Evactron or similar decontamination device) will not work for you properly.
Plasma cleaning will help for a typical carbon coating. You may have to mill the carbon away with a FIB, but good luck, as Carbon is quite resilient to the FIB beam. Curious to know results!