Rightclick contact > plus extras > rename contact...give contact custom name, highlight it..hit ctrl+k, choose color <enter>
If you wanna keep the name your contact uses use (!N) as customname, this tag will show whatever name your contact uses and you can colour it just as any other custom name