Hall effect sensors

HW sounds OK.

A look at the numbers of the first output shows that there are only a few numbers occurring for RPM and that they seem all to be multiples of 594 apart.
This is caused by the constant duration of 101 milliseconds and the constant in the formula of 60000

x * 60000 / 101 <==> x * 594 so that explains the step-size in the output.

This implies if you measure every second you wil get a stepsize of about 60. btw doing the math in micros will not change this substantially

If you set the interrupt on CHANGE you would get two IRQ's per rotation. That would improve the accuracy (in theory 2x if pulses are symmetrical)
combined with a timing of 1 second would give a stepsize of about 30.

//
//    FILE: rpm.pde
//  AUTHOR: 
//    DATE: 20-oct-2012
//
// PUPROSE:
//

volatile unsigned long rpmcount = 0;
unsigned long previous = 0;
unsigned int rpm = 0;

unsigned long time = 0;
unsigned long timeold = 0;

void setup()
{
  Serial.begin(115200);
  attachInterrupt(0, rpm_fun, CHANGE);
}

void loop()
{
  time = millis();
  if (time - timeold >= 1000)
  {
    unsigned long duration = time - timeold;
    timeold = time;
    unsigned long rounds = rpmcount;
    rpm = ((rounds - previous) * 30000UL / duration); 
    previous = rounds;
    // DO THE OUTPUT
    // comma separated allows you to copy the output into excel
    // and make a nice graph
    Serial.print(duration);
    Serial.print(", ");
    Serial.println(rpm);
  }
}

void rpm_fun()
{
  rpmcount++;
}

If the baudrate influences the RPM it might be that the wires influence each other.
You could check if you have the same problems if you take IRQ1 (pin 3)

================

What is strange is that the numbers are much higher than you expect [about 5000]. Is this correct?

Do you have a datasheet of the reed switch used?
What is its upper switch frequency?