PID Tune Problem and Clarification

Here is a screen shot of a HalScope plot of some parallel port inputs, two of witch are the A-B inputs for a software encoder. In this shot it is fairly obvious that I have a serious noise problem. On the A and B inputs (the green and blue traces at the bottom) you can see both true pulses, the long ones, and the noise pulses, the short spikes for only 1 thread period or so that show up simultaneously on several input pins.