It sounds like the PWM motor current is interfering with the signal from the encoders. What are you using to drive the motors, and how do you have the encoders connected?
You may need to use screened (shielded) cable to connect the encoders to the Arduino, and you should definitely ensure that the power and ground lines to the encoders are completely separate from the power and ground lines to the motors or motor drivers.