Driving a DC motor /w 16f84a

[skimask]

It says the gate threshold voltage is from 2v to 4v.

If we're both reading the same datasheet, then you may also notice that in this case, it says that the gate voltage (Vgs) is equal to the drain-source voltage (Vds) and the current (Id) is only 250uA.
In your case, you're probably trying to draw too much load without enough Vgs (see Figure 5,6,7 of the datasheet).
You would want to find a 'logic level' n-channel enhancement mode mosfet with enough current capability at low gate threshold voltages.
I use an STN2E10L (sot-223 package) in most of my stuff. I can pull over 5 amps thru it @ 5v using a 5v (which ends up being about 4.5v) PIC pin to drive it.