finding the $n$ closest pairs between $2n$ points

What you're looking for is a minimal weight perfect matching on a complete graph. From a quick wikipedia search, I think Edmonds' matching algorithm will do the trick for you (see the bottom of the page) - I think it's polynomial time in the number of nodes.

Actually, the OP is on a slightly different problem: the Euclidean minimal matching problem, where the complexity should be a lot better. See The Open Problems Project, Problem 6 (we will probably hear more from Joseph...). EDIT I also found this paper which seems to be much simpler than Edmonds, while not being particularly 2D-oriented.