It's not as easy as it first seems to divide the quadrature signal from an encoder like that. The number of pulses on the encoder isn't really the limit per se, it's the frequency at which the chip can count the pulses. So the faster you want to go the lower resolution you'll have to use. Are you saying that it doesn't work at all without the divider either or are you loosing position and getting O-counts as the speed increases.
Start slow and work your way upwards and see where the problem starts. I've found that 130kHz is about max what I can achive with my HP-UHU. So if your setup is about equal to mine you should be able to reach 975rpm with 2000 lines encoders (8000ppr in quadraure).
USDigital sells a quadrature divider called EDIVIDE and there's also some open source project available that uses a small Atmel uC to do the quadrature dividing. Even so I say it's better to either live with the reduced speed or buy new encoders.