I had a lot of problems with the 800 and the HDTivo. I found part of the problem to be my positioning of the emitter from the 250 base unit and actually a bad remote.(after a lot of trouble shooting) Are you using the rf base station or another type of ir receiver? Have you changed emitters, are they all the same type?
You can try learning the remotes from diferent distances, also try a piece of white paper inbetween.
Do you have access to an mx700? You can try the ir database, then try and program the 500 or 600 with that one. That has helped me in the past.
Good Luck,
Mike