Okay, in season 3, when Stringer wants Clay Davies killed, as he heads into Avon's "office", he says, "Slim Charles? Who the fuck is Slim Charles?" (to illustrate how out-of-the-loop with Avon he's become).
In the first episode of the same season, when the Barksdales are having their "board meeting", String says: "Chair recognises Slim Charles," i.e, already on first/nickname terms.
I bet this has already being pointed out, hasn't it? Or I bet I'm misremembering it.