I think they basically mean the same. It seems to me that a person supposed to be just ought to be just, while a person supposed to be fair should be fair. Therefore, they are used in different contexts (in court or in a football match).
I like this guy's take, which is similar to PMEffEmDoubleyou's (and others'):
Originally Posted by Principles of Justice
In the context of intractable conflict, the terms 'justice' and 'fairness' are often used interchangeably.
Taken in its broader sense, justice is action in accordance with the requirements of some law. Some maintain that justice stems from God's will or command, while others believe that justice is inherent in nature itself. Still others believe that justice consists of rules common to all humanity that emerge out of some sort of consensus. This sort of justice is often thought of as something higher than a society's legal system. It is in those cases where an action seems to violate some universal rule of conduct that we are likely to call it "unjust."
In its narrower sense, justice is fairness. It is action that pays due regard to the proper interests, property, and safety of one's fellows. While justice in the broader sense is often thought of as transcendental, justice as fairness is more context-bound. Parties concerned with fairness typically strive to work out something comfortable and adopt procedures that resemble rules of a game. They work to ensure that people receive their "fair share" of benefits and burdens and adhere to a system of "fair play."
I think that fits reasonably well with the connotations of just vs fair. Fairness is more context-dependent and limited in scope, while justice is more concerned with the consistent application of (possibly universal) laws and principles.