I had the same problem, you have to set it in two places. Once under registered servers and once under Options>> when you change connections.

SQL server 2008 R2. Picked a random color to test and now cannot change it back. Even after deleting the server registration, the color stays at the ugly...