Ok, that does not look right. I can reproduce the problem on OS X, MMA 10.0.2, too.

This command is a workaround:

RandomChoice[Select[Range[100000, 500000], PrimeQ], {2, 2}]

but it is about 100 times slower.

This one is as fast as the original:

Prime@RandomChoice[Range[PrimePi[100000], PrimePi[500000]], {2, 2}]

Cheers, Marco

Watch this:

     RandomPrime[{100000, 499999}, {2, 2}]
         (* {{246251, 287611}, {415111, 277003}} *)

and now

     RandomPrime[{100000, 500000}, {2, 2}]
              (* {{457889, 394619}} *)

And additional observation: There are 2 prime numbers between 499,970 and 499990

     PrimePi[499999] - PrimePi[499970]
     (* 2 *)

So RandomPrime[{499970, 499999}, {2, 2}] returns these 2 numbers twice {{499979, 499973}, {499973, 499973}} since we asked for 2 by 2 output. But RandomPrime[{499970, 500000}, {2, 2}] returns these 2 numbers one time {{499973, 499979}}. Very strange why it does this when the top range goes over 499999.

So, I would say it looks like a bug.
Version 10.02, on windows 7, 64 bit