The issue is that Plinq has quite a large amount of overhead. Its very useful for computationally intensive projections, what you have IS NOT computationally intensive.
Firstly. PLinq will NOT parallelize the GetNextPair part of the linq query. You can try placing a break point into that function and bringing up the Thread window to check which thread is running it each time.
Secondly the part that IS actually parallelised is the
.Count(tuple => tuple.Item1*tuple.Item1 + tuple.Item2*tuple.Item2 <= 1d)
part, which is basically
.Where(tuple => tuple.Item1*tuple.Item1 + tuple.Item2*tuple.Item2 <= 1d)
.Count()
The where part is going to work quite easily. However, the dispatching to each thread to run the predicate is going to have quite an overhead.
The count part then would require a map reduce, again, could have quite an overhead.
So the only way you could have a speed up is if the predicate is computationally more intensive than the overhead of scheduling the predicate and then map reducing the result.
Try whacking in a Thread.Sleep into the predicate...