First off, I am running this on a dual core 2.66Ghz processor machine. I am not sure if I have the .AsParallel() call in the correct spot. I tried it directly on the range variable too and that was still slower. I don't understand why...
Here are my results:
Process non-parallel 1000 took 146 milliseconds
Process parallel 1000 took 156 milliseconds
Process non-parallel 5000 took 5187 milliseconds
Process parallel 5000 took 5300 milliseconds
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace DemoConsoleApp
{
  internal class Program
  {
    private static void Main()
    {
      ReportOnTimedProcess(
        () => GetIntegerCombinations(),
        "non-parallel 1000");
      ReportOnTimedProcess(
        () => GetIntegerCombinations(runAsParallel: true),
        "parallel 1000");
      ReportOnTimedProcess(
        () => GetIntegerCombinations(5000),
        "non-parallel 5000");
      ReportOnTimedProcess(
        () => GetIntegerCombinations(5000, true),
        "parallel 5000");
      Console.Read();
    }
    private static List<Tuple<int, int>> GetIntegerCombinations(
      int iterationCount = 1000, bool runAsParallel = false)
    {
      IEnumerable<int> range = Enumerable.Range(1, iterationCount);
      IEnumerable<Tuple<int, int>> integerCombinations =
        from x in range
        from y in range
        select new Tuple<int, int>(x, y);
      return runAsParallel
               ? integerCombinations.AsParallel().ToList()
               : integerCombinations.ToList();
    }
    private static void ReportOnTimedProcess(
      Action process, string processName)
    {
      var stopwatch = new Stopwatch();
      stopwatch.Start();
      process();
      stopwatch.Stop();
      Console.WriteLine("Process {0} took {1} milliseconds",
                        processName, stopwatch.ElapsedMilliseconds);
    }
  }
}