Resolution. Called DirecTV and told them of my problem. I switched remotes to no effect. I was then told of the hard drive corruption potential due to something that went wrong in their downstream. Although I couldn't imagine why this would reduce the range of the remote, I was asked to try running a hard drive error check before being sent a new receiver. Amazingly, it seems to have worked. Now my remote works both at range and much quicker in general.
Procedure: Reset with red button. Upon seeing "Almost there. A few more seconds please", press and hold Down and Record on the receiver itself. Hold these until you get the screen telling you its scanning the hard drive. This seems to perform effectively a (Windows) chkdsk /r on the hard drive. It takes around 2 hours (I turned the TV off @ 54% and went to sleep before it finished). It will tell you errors found and errors corrected, but I didn't see any before calling it a night.
I did not lose any recordings or my scheduled recordings... I may do this on all my receivers just for a potential performance upgrade. Can't really hurt.
This was on my HR21-700. RF works flawlessly again. Yay!