The Sept 4, 2005 New York Times reports on a study in Animal Cogntion that suggests birds have theory of mind. At least, they can separate "what I know" from "what the other bird knows" -- as indicated by one bird's pretending to eat to eat cheese so the other bird wouldn't steal the cheese later.
There are some other examples in the story, too, and it contains a good, simple explanation of "theory of mind".
The link above may not work after such a long delay, but here's the full citation in case you want to track down the article:
NYT Magazine: Deceit of the Raven // By DAVID BERREBY, September 4, 2005
It turns out that even birds know how to cheat and read minds. Is there any way that humans can preserve their sense of uniqueness?
(but wait: birds eat cheese?!)