Redheads and pain receptors
I think it's best to break this question up in to two parts:

What mutations account for red hair and fair skin in humans
How might these same mutations affect pain sensation

MC1R variants &amp; red hair
The MC1R gene encodes a transmembrane receptor protein (belonging to a very common family of receptors), called melanocortin 1 receptor. It also has another name describing its best known role in the body: 'alpha melanocyte stimulating hormone receptor'.
This receptor binds ligands - both agonists and an antagonist - outside the cell, and passes signals to the pigment-producing pathways in melanocytes; activation favours eumelanin (brown) production over pheomelanin (red).
Common MC1R variants are all single point mutations which cause an amino acid substitution and reduce/impair the normal function of the receptor - i.e. loss-of-function mutations. E.g. Arg151Cys, Arg160Trp, Asp294His, the most common variants in european red-heads probably arose ~80,000ya in a eurasian population, and have a reduced ability to activate adenylate cyclase inside the cell.
How &amp; why could the same mutations affect pain sensation?
Genetic linkage, or dual role of MC1R?
Firstly, it is possible that MC1R variants are linked to a mutation at a separate nearby gene; the two making a haplotype.

In this diagram, mutation A might be a red-hair MC1R mutant, and mutation B might be some other pain-sensitivity mutant. Through random effects on small populations, group Hg B might have 'seeded' the european population, say; meaning that the two mutations are inherited together in that population. If the two loci are very near, their linkage is less likely to be disturbed by recombination.
This is an obvious possibility whenever two seemingly unrelated traits co-occur.
However, there's good reason to believe that this case is due to a dual-role of MC1R...
Arguments against linkage; for dual role of MC1R: The existence of many different haplotypes in redheads argues against linkage, if this pain sensitivity effect is found across all/many redhead haplotypes, and not in wildtype MC1R europeans.

Indeed, this study shows that europeans with 2 MC1R mutant variants (homozygote or compound-heterozygote) have increased pain tolerance to electric shocks compared to people with 1 or more functional copies of MC1R. The second panel shows that a mu-opiod analgesic (morphine) has greater effect on those with no functional MC1R. The effect coincides with presence of functional MC1R, not a particular haplogroup.
MC1R is also expressed in a region of the midbrain responsible for pain modulation. This region produces endogenous opioids to control pain. As far as I can gather, researchers are trying to work out what exactly it does there.
The study by Mogil et al suggests MC1R in the brain somehow counteracts pain inhibition by the opioid receptors, and so MC1R mutant redheads have more effective ex/endogenous opioid pain inhibition, which reduces noxious pain.
This study found that redheads are slightly less susceptible to pain-sensitisation by capsaicin.
Whereas this study found a contradictory result, that redheads are more sensitive to thermal pain and that lidocaine is less effective for them. (This study didn't genotype the subjects, and red-hair may be caused by mutations in other genes.)
Overall, the number of subjects in these studies (both humans and mice) is fairly small; and the science of MCR pain modulation seems early-days.
But at least we can answer your question: the mutations apparently responsible for red hair and altered pain sensitivity are amino acid substitutions in MC1R causing loss-of-function variants.
The fact that MC1R probably has totally different roles in the brain and in the skin is an interesting general point of biology.

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1288200/ &lt; about the evolution of MC1R mutant variants.
http://www.ncbi.nlm.nih.gov/pubmed/10403794/ &lt; about the mechanism of loss-of-function
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1736101/pdf/v042p00583.pdf &lt; evidence of increased pain tolerance &amp; greater morphine effectiveness
http://www.scandinavianjournalpain.com/article/S1877-8860%2810%2900111-4/abstract &lt; evidence of resistance to hyperalgesia
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1692342/ &lt; evidence of decreased pain tolerance &amp; lesser lidocaine effectiveness