Why do some pins have a different PWM frequency?
Those aren't the only frequencies available for the PWM signals. However, they are the frequencies as determined by the applied prescaler (which you can readily change as detailed below).

Each of the 3 pairs of PWM pins is tied to one timer, each of which has its own base frequency, as follows:


Pins 5 and 6 are paired on timer0, with base frequency of 62500Hz
Pins 9 and 10 are paired on timer1, with base frequency of 31250Hz
Pins 3 and 11 are paired on timer2, with base frequency of 31250Hz


Then each set of pins have a number of prescaler values that can be chosen, that will divide the base frequency of that pair of pins. The prescaler values available are:


Pins 5 and 6 have prescaler values of 1, 8, 64, 256, and 1024
Pins 9 and 10 have prescaler values of 1, 8, 64, 256, and 1024
Pins 3 and 11 have prescaler values of 1, 8, 32, 64, 128, 256, and 1024


The different combinations yield different frequencies in a given PWM pin. Notice that timer 2 (tied to pins 3 and 11) have more prescaler values available, resulting in more frequencies available.

Now, why timer 2 is different, that's a separate question.

Edit: Here's a list of possible PWM frequencies per pin (from this article):


  For pins 6 and 5 (OC0A and OC0B):
  
  
  If TCCR0B = xxxxx001, frequency is 64kHz
  If TCCR0B = xxxxx010, frequency is 8 kHz
  If TCCR0B = xxxxx011, frequency is 1kHz (this is the default from the Diecimila bootloader)
  If TCCR0B = xxxxx100, frequency is 250Hz
  If TCCR0B = xxxxx101, frequency is 62.5 Hz
  
  
  For pins 9, 10, 11 and 3 (OC1A, OC1B, OC2A, OC2B):
  
  
  If TCCRnB = xxxxx001, frequency is 32kHz
  If TCCRnB = xxxxx010, frequency is 4 kHz
  If TCCRnB = xxxxx011, frequency is 500Hz (this is the default from the Diecimila bootloader)
  If TCCRnB = xxxxx100, frequency is 125Hz
  If TCCRnB = xxxxx101, frequency is 31.25 Hz 
  


TCCRnB is where you set the prescaler bits for timer n, replacing n by 0, 1 or 2, depending on the timer you want to set. If you are still unsure about bitwise operations, read this bit math tutorial.

My sources:


http://playground.arduino.cc/Code/PwmFrequency
http://arduino.cc/en/Tutorial/SecretsOfArduinoPWM
http://arduino.cc/en/Tutorial/PWM
http://arduino-info.wikispaces.com/Arduino-PWM-Frequency


Note that there seems to be divergence in those sources about whether pins 9 and 10 have the same behavior as 5 and 6 or 3 and 11, but you get the idea anyway. I'm reading the datashet to try and figure out which is correct, or whether this is a difference between boards.