To get this to always work, there are TWO places to set it:

1. On a registered server, select the "Connection Properties" tab, and set the color.

2. On the Object Explorer, if you click on connect and select a server, you will need to set it there on the "Connection Properties" tab also - it doesn't pick up the color from an associated registered server of the same name.