There are two (possibly more) potential problems that might result in the 
reported problem results:

1) When using flooding (as opposed to dipping) for decolorizing with such 
volatile solvents the tissue section may dry. True gram positive staining 
will decolorize under such conditions. We never had any problems with 
demonstrating gram positive when we used the Macullum Goodpasture method 
(aniline oil and xylene decolorizer) but when we switched to the 
Brown-Brenn with ether-acetone decolorizer we began to experience gram 
positive "fading." When this occurs, the organisms pick up the red and can 
be mistaken for gram negatives.

2) The iodine is extremely important. If the iodine becomes weak, contains 
a precipitate (usually from refrigerating), runs off before it has been on 
the slide long enough or becomes diluted from other reagents or excess 
water left on the slide prior to flooding, you will experience almost 
identical results. As an aside, I've never been able to over-expose the 
slides to iodine. Before we were more rigorous in our procedure controls I 
used Lugols (more concentrated) instead of the Gram's  to protect my stain 
from whatever insults another tech may have perpetrated on the working 
Gram's iodine jar.

Bert