In this context, we generally use it in the order it was originally given. "I saw traces of blood on the walls" not "I saw blood traces..."
Whilst normally it would be "trace of + noun" we do say "traces of + colour". "Under the pink paint, you could see traces of blue", where it is unnecessary to specify "blue paint". In your example, it effectively means "I spotted traces of [something] red and [something] sickly green".