OK, I can explain this one. The thing is, there is no reliable one-to-one correspondence between these Italian particles (like "di," "da" or "of," "by" etc), so you can never assume that, just because in many situations "di" is transated as "of," it will be always translated this way. If you make such an assumption, you will always be confused. In this case, think of "di" meaning (kind of) "with," as if in Italian, instead of saying "He replied 'yes'" you had to say "He replied with 'yes'." It actually kind of makes sense that way.
To understand better, you can make an analogy: Everytime I ask him to go to the movies, he answers THAT he can't go. He answers [THAT] no. <-- This "[THAT]" is not used in English, that's why it sounds strange to say "di no" in italian. I understand that the "no" is replacing the "he can't go", so that's why we use "di" in italian.
In other languages this happens as well: I think so Io credo di sì (italiano) Eu penso que sim (português) Je pense que oui (français) Yo creo que sí (español)