I usually consider PatternTest as local to a specific pattern such as x_Integer?Positive and Condition as more general, often involving multiple patterns, e.g.:
f[x_, y_] /; x+y < 10 := x*y
An aspect of PatternTest that is different from Condition is that it is automatically applied to each element of a sequence, whereas Condition applies to the whole. A pattern such as __?EvenQ means a sequences of arguments all of which pass EvenQ. Consider:
f2[x__?EvenQ] := . . .
This is awkward with Condition:
f1[x__] /; (And @@ EvenQ /@ {x}) := . . .
Furthermore the naive method above does not short-circuit on a failure therefore it will be inefficient. This could be fixed but it will be even more clumsy.
Then consider the converse:
f3[x__] /; Plus[x] == 7 := . . .
I can think of no way to do this with PatternTest. (Because as stated above each element of the sequence is tested independently.)
There is one rather obscure (at least to me) yet very important use of Condition that extends this generality.
lhs := Module[{vars}, rhs /; test] allows local variables to be shared between test and rhs. You can use the same construction with Block and With.
This is quite unusual in Mathematica's patterns and assignments. It allows execution of code as part of the definition, then testing by a condition based on the result. If the condition fails, the pattern matcher then moves on to search for other matches. The evaluation that occurred can produce side effects but otherwise Mathematica behaves as though the entire pattern (lhs := rhs assignment) did not match.
One elegant use of this functionality is the Trott-Strzebonski method for In-Place Evaluation.
Leonid wrote, and encouraged me to include here:
One other thing I want to mention is that with PatternTest, it is easier to inadvertently leak evaluation, while in Condition avoiding that is usually just a matter of inserting Unevaluated in a proper place. I discussed this topic to some extent here
Finally, there are some syntactic differences which are good to keep in mind, for example precedence-related issues like this one.
Rojo stated:
Another consequence of this shows when you want to store a pattern in a variable, or inject it with a With. ... Can't do that with Condition unless you want all the instances of the pattern in each definition to be the same.
As a rather contrived counter-example one can use Unique symbols in a pattern constructor:
pat[] := Pattern[#, _] /; # > 4 & @ Unique[] f[a : pat[], b : pat[]] := {a, b} f[5, 6]
{5, 6}
Of course it is better to use PatternTest for this, but I think it is useful to show that it can be done.