Well, some non-obvious things here (at least as far as I could find out):
PrimeQ[x] gets evaluated immediately to False, before any number can be even tried;Reduce[] seems to expect a system of equations and inequalities only;
So - here is my approach:
primeQ[x_?NumericQ] := PrimeQ[x]
Reduce[NextPrime[x] - x == 2 && 0 < x < 20 && primeQ[x] == True, x \[Element] Integers]
