Tested on Firefox and Chrome and Confluence 5.9.2.
This issue is not present when running Safari.
When users are running Firefox or Chrome the unused links in the sidebar seems to ignore the custom color settings. They still show up as blue default color. When clicked once, they gain the custom color.
When running Safari all seems to work well.