Eric, can you test your scenario with Emacs 24.5, please?

The problem also happens in 24.5.  

I also noticed that, once the problem has happened, if I close the emacsclient frame with C-x 5 0, then create another one with TERM=xterm-256color, the colors in the *Colors* buffer are restored.