In my case I assign a Custom Color Group to each of my tags. After creating my color groups I assigned them to the appropriate tag in the Edit tag option and each message line then shows the color.

I think you need to create customer color groups in order for the whole line to change color.  If you only assign a color to the tag it won't change the line color but will only display the color when Tags are shown in the columns.