I suppose it may have gone back to the old color if I was in a range where there were few dye colors to chose from. However, it happened while I was feeding only pears and apples. I didn't stop on a fruit with no message though.
I suggest:
Apples x3
Berries x2
Again, start feeding berries or apples until you see a feather message. Count that towards the above. After that, continue to count ONLY fruits that yield the new feathers message towards the above recipe. Also, make sure the stable condition is Good.