Sounds like poor electrical contact. The poor contact could come at many points. Here is a list.
1. Dirty wheels. Check and clean if needed.
2. Poor contact between the trucks and the phosphor-bronze pickups - could be caused by dirt between the contact "fingers" on the truck and the phosphor-bronze pickup; could also be caused by insufficient downforce on the strip. Clean everything (a wire brush in a Dremel would be ideal; otherwise, use 90% alcohol and if anything looks oxidized, clean with 400-grit sandpaper) and bend the pickup strips down some to provide better contact force to the truck.
3. Poor contact between the frame and decoder board. This is a common problem with "drop-in" boards. To check this, wedge something between the board and frame (folded paper or cardstock) to put upward pressure on the board where the pickup pads on the board contact the "fingers" on the frame. If this solves your problem, the next step would be to put a thin coat of solder on the pickup pads to make them slightly thicker.
4. Poor contact between the motor brush contact strips and the pads on the bottom of the decoder that contact these pickup strips. First, make sure they are clean (again, if there is any oxidation, clean with some 400-grit sandpaper and 90% alcohol). Then bend up the motor contact strips so they will put more pressure on the contact pads on the board.
Given the behavior you describe, 1 and 2 are less likely the problem than 3 and 4, but to truly eliminate all the possibilities, follow the above in order.
If you still have problems after all of the above, you may have a bad decoder board. Replace, either with a TCS or Digitrax drop in, or with a hard wired decoder (my preference, but I'm a bit crazy about potential electrical pickup problems and hard-wiring eliminates many of the failure points).
John C.