Don’t know if this helps… I’ve been experiencing this repeatedly within a single folder (therefore a single .DS_Store file). The problem occurs about 10-15% of the time.
I’m having the same issue and as of today I can’t seem to ever make the new color stick. I’ve quit Total Finder and can color the labels no problem. I"m running TF 1.5.19 in os x. 8.5.