The latest issue of Proceedings of the Royal Society B (biological sciences) has a paper with evidence that chimpanzees have a sense of 'fairness' dependent on whether the parties already know each other. Here's the abstract from the Royal Society's website:

Tolerance for inequity increases with social closeness in chimpanzees by SF Brosnan, HC Schiff and FBM de Waal

The evolution of the sense of fairness may have involved the strength of social connections, according to researchers at the Yerkes National Primate Research Center in Atlanta. Sarah Brosnan and Frans de Waal observed variability in chimpanzees’ responses to inequity depending on the strength of their social relationships. Chimpanzees in a close, long-term social group were less likely to react to unfair situations than were chimpanzees in short-term social groups. This is the first demonstration that reactions to inequity in nonhuman primates parallel the variation in the human response to unfair situations that is based on the quality of the relationship.

Similar findings have previously been reported in capuchin monkeys. Note that 'unfairness' in these experiments is primarily unfairness to the animals themselves whose response is being studied, not to other animals. If they don't get their 'fair' share they sulk, but this new reseacrh indicates that they are more likely to tolerate unfairness (to themselves) if the beneficiaries are regular social partners.

Whatever the details, this research does indicate that at least the rudiments of a sense of 'justice' are found in non-human primates, which makes it difficult to argue that this is entirely a product of human cultural evolution.

Addendum from Razib: Article in Nature.