By diffing our system information, I noticed three add-ins I had my colleague didn't (JetBrains TeamCity Addin 7.1, VisualSVN 3.0.5 and Git Extensions).
Trying to disable them one by one I found out the culprit is the add-in for TeamCity: as soon as I uninstalled it (it's not reported in Visual Studio, and you can't disable it) the color scheme fixed itself.
The funny thing is both ReSharper and the TeamCity add-ins are provided by JetBrains.