The worst-case high level output (2.4V) is given at 20mA load, whereas the Arduino presents only a tiny load. So I very much doubt that insufficient high level output voltage is the problem. Nevertheless, I suggest you change the pin mode of the two encoder input pins to INPUT_PULLUP to be safe.
My guess is that one of the four wires between the encoder and the Arduino is not properly connected.