Most pulsars have periods around a second, and are spinning down very gradually. A few are clearly young (still hot, still in a supernova remnant, spinning down rapidly) and are faster, with periods as short as several tens of milliseconds. But there are other pulsars that are even faster - periods down to 1.4 milliseconds, that is, spinning some seven hundred times a second - and yet appear to be very old: cold, spinning down very gradually, very weak magnetic field. These are called millisecond pulsars, and it was a puzzle where they could possibly come from.
The key clue to the puzzle was their binarity. Most stars are found in systems of several stars orbiting each other. But pulsars are usually solitary. This is mostly because of their violent births: to make a pulsar, the star has to go supernova, and such a violent explosion tends to break up binary systems. It doesn't always break them up, though, and so some binary pulsars are known. If you look at the millisecond pulsars, though, most of them are actually in binary systems, unlike the normal pulsars (see the graph at right, based on the ATNF pulsar database). So we think the presence of a companion is key to making a millisecond pulsar.
The story, as we understand it, is this: A pulsar forms in a supernova. It is either in a binary system which survives, or it captures a companion. It lives out its life as a pulsar, spinning down gradually past the point where it is visible as a pulsar. The system stays like this for a long time. But eventually, one of two things happens: the companion starts to swell up into a red giant, or the orbit shrinks. In either case the system reaches a point where some of the matter at the surface of the companion is attracted more strongly by the neutron star than by the companion. This matter then falls down onto the pulsar.
Pulsars are not much more massive than the Sun, but they are much much smaller. So when matter falls onto one, tremendous amounts of energy are released. But remember that the two stars are in orbit, so the system is rotating. If you take a piece of matter from the companion, it will carry some angular momentum with it. To make the obligatory analogy, just as when a figure skater pulls in her arms, she speeds up, when you take matter from the companion and bring it in to the neutron star, the matter begins to rotate more rapidly. When this matter falls on the star, the star is spun up a little. I am glossing over numerous important details here, but the point is, when you start transferring mass to a neutron star, it is possible to spin it up.
So, we think that millisecond pulsars are old pulsars that have spun up, or "recycled", by accretion of mass from a companion. Observationally, we see systems where mass is being transferred: they're very bright X-ray sources. In a few cases we can actually tell how fast the neutron star is rotating, and sure enough, its period is down in the millisecond range. But these systems don't produce radio pulsations, presumably because all that matter falling in either blocks the radio waves or shorts out the emission mechanism (which needs a near-vacuum in the magnetosphere). So to make millisecond pulsars you need somehow to turn off the accretion and clear out all the matter, so that the radio pulsations can emerge. This transition hasn't been seen before, and the theorists have some difficulty explaining the population of objects that we see - while we see both millisecond pulsars and their hypothetical accreting progenitors, none of the progenitors seems to be positioned to turn into anything like the millisecond pulsars we actually see. So that last step, accretion turning off and radio pulsations starting, remains something of a mystery.