Manually specifying distance metric to Nearest slows down calculation

In this case Nearest simply has no code in place to use its fast octree approach with metrics other than Euclidean. This is, admittedly, a shame, because other $\ell_n$ spaces could in principle be supported in the same way. In particular $\ell_\infty$ (aka chessboard) is quite amenable to that underlying technology, but it just has not been implemented thus far. It is in our suggestions data base to do this, by the way (I put it there almost three years ago).

If you feel up to rolling your own octree variant for a chessboard Nearest, some of the responses here might be of use.

This is usual in Mathematica: supplying comparison functions tends to slow things down, probably because of having to come up from the kernel to execute user-level code. Example:

lst = RandomReal[{-1, 1}, 100000];
AbsoluteTiming[Do[Sort[lst], {i, 10}];]
AbsoluteTiming[Do[Sort[lst, OrderedQ[{#1, #2}] &], {i, 10}];]

(*
{0.190045, Null}
{13.598207, Null}
*)

Looks like @DanielLichtblau's speed improvements made it into M10:

data1=RandomReal[10,{10^3,3}];
data2=RandomReal[10,{10^3,3}];

nf1=Nearest[data1];
nf1/@data2;//AbsoluteTiming

nf2=Nearest[data1,DistanceFunction->EuclideanDistance];
nf2/@data2;//AbsoluteTiming

nf3=Nearest[data1,DistanceFunction->ManhattanDistance];
nf3/@data2;//AbsoluteTiming

nf4=Nearest[data1,DistanceFunction->ChessboardDistance];
nf4/@data2;//AbsoluteTiming

{0.001588, Null}

{0.001529, Null}

{0.00141, Null}

{0.001215, Null}