The DOF will increase, but not entirely with the crop factor, however, I just learned that it converges to that in certain cases.

Your distance increases by the crop factor, but the DOF doesn't follow a linear curve, which means that the increase on DOF as a factor depends on the distance you start at. An important factor is Circle of Confusion which is the real world "blur" that is projected on the sensor plane. How you view this will affect your aim for it.

When viewing in pixel space, you need to worry about the CoC relative to pixel cell size multiplied by magnification (viewing "fit to screen e.g. at M=0.25, your CoC may be 4x4 pixels). Ie. din't worry about sensor size. But if you view on a print in real world, you need to worry about the magnification given by print size/sensor size, and in this case you magnify crop factor more. So you work out the CoC as a function of print size and view distance, and divide by Magnification , where Mcrop = Mff*1.6. Thus CoCcrop = CoCff/1.6. So the figure below is for the print situation where you use the crop factor on CoC.

Source: http://www.elsners.org/wordpress/

Here is the complex nature of how the DOF evolves with distance:

Source: http://www.cameratechnica.com/2011/06/12/alternatives-to-the-one-third-rule-for-landscape-photography/

With dof master you can do some numbers on crop and fullframe camera. If you start from close range,10cm, the Dof factor is 3.5 if you keep the same CoC, 2.5 if you pick a Canon FF vs a Canon 1.6x crop, with 50mm 1.8. As you increase the distance, the numbers evolve like this:

10cm FF vs 16cm Crop: 2.5 
1m FF vs 1.6m Crop: 1.75 
10m FF vs 16m Crop: 1.63 
50m FF vs 80m Crop: 1.66 

(These numbers normalize the CoC to the sensor.)

So it seems even though the formula is not linear, it converges to a linear segment at higher distances, with the crop factor (assuming it is correct to normalize the CoC). Definition of high is distance >> focal length.

You learn something every day..

I looked further into it, and I used the formula for DOF with distance >> focal length. I insert CoC (c) and distance (s) for crop sensro with the same lens, and in the case of print size based CoC, where crop CoC = FF coc / 1.6 and crop distance = ff distance *1.6:

And for Nikon replacex1.6 with x1.5.

I am amazed. But remember the formula is for the special case of s >> f. And the CoC factor for screen size is not the crop factor, unless you compare a FF and Crop sensor with equal resolution.