There does indeed appear to be some form of paradox here, but it is very subtle.
To be completely clear, I'm assuming the game proceeds in rounds. In each round, a neutral umpire randomly chooses one of the players and directs him to tell another random player whether he knows yet who the thief is. The recipient of that information then immediately makes all the inferences he can from this knowledge before the next round. The third player, who was not party to the communication does not know what was said and does not even know a round took place.
First off, a few simple facts: If you know you're innocent, and you hear anyone else say they don't know who the thief is, then by elimination you now know that the third person is the thief. Therefore if you ever tell anybody "I don't know", the only thing they can subsequently tell you is "I know who it is". So that won't make you any wiser.
Now, let us ask:
(1) If you know you are innocent and the first thing that happens to you in the game is that someone tells you "I know who the thief is", can you conclude anything?
Of course it is possible that the person who spoke to you is the thief, so the real question is whether it is possible that he is innocent. A priori it sounds conceivable that the two other guys may have communicated without you noticing, such that the innocent among them now knows.
However, how could that communication go? One of them must have spoken first. If the innocent one spoke first, then (as argued above) he will never get any information out of the thief that's useful to him, so he will not end up knowing.
On the other hand, if the thief spoke first, then the innocent guy would have found himself in exactly the situation described by (1) above. And now we're in trouble:
If the correct answer to (1) is "yes", then it is possible that the other innocent guy learned from the thief who the thief was, and therefore you can subsequently be told by either the thief or the other guy that they know. Therefore the correct answer to (1) is "no".
On the other hand, if the correct answer to (1) is "no", then there is no way the other innocent guy could ever know who the thief is, as long as you haven't communicated with either of them. And therefore if one of them admits to knowing, they must be the thief. So the correct answer to (1) is "yes".
Thus, the answer to (1) can be neither "yes" nor "no". A paradox!
I think the resolution to this is that this reasoning depends critically on the assumption that nobody ever knows whether the first communication they are part of is the first round of the game or not. That's a critical part of the argument that the answer to (1) depends on a previous answer to the same question.
On the other hand if somebody knows it's the very first round of the game when someone tells them "I know who it is", then they can comfortably conclude that they must be the thief.
And contrariwise, therefore, if somebody knows it's the second round of the game when they're told that, then they know they can't conclude anything.
So really what enables the paradox is the assumption that time is continuous (or at least dense): no matter how quickly after the game starts we get a message, it is in principle possible that the two other guys may already have talked.
Thus, we might categorize the paradox as a time-reversed cousin of the surprise exam paradox.
Further, I suspect that trying to formalize the paradox (in some appropriate variant of temporal+epistemic logic) will run into trouble with expressing the assumption that everyone are perfect logicians, and everyone knows that everyone else are perfect logicians, and everyone knows that too, et cetera ad infinitum. Even defining what "perfect logic" should mean seems to require a powerful enough reasoning system that Gödelian incompleteness kicks in and tells us that in that case there is no such thing as a perfect logician, at least not one that can be reasoned about.