From the
Grove_-_Dust_sensor datasheet, it looks like the sensor already has a 10K pullup resistor.
Output Method Negative Logic, Digital output,
Hi : over 4.0V(Rev.2) Lo : under 0.7V
(As Input impedance : 200k) OP-Amp output, Pull-up resistor : 10kIt doesn't look like they're using a rail to rail op-amp. From the characteristics, I suspect the output signal at the sensor itself is rather weak with poor rise/fall time. A weak signal to begin with might explain why it doesn't take much cable length to cause issues.
I would still try adding a pull-up resistor of 10K at the Arduino input. Note that they don't specify the max output current of the op-amp, so lowering this value too much will either overload the output or lift the minimum voltage to a value where the Arduino considers it continuously HIGH.
Images of the PPD42NS dust sensor's PCB the web reveal a 14-pin surface mount op-amp If this is non rail-rail type, then the minimum output current from the remaining op-amps available at Digi-Key is 4mA. This would indicate that its safe to use a pullup as low as 3.6K.