Ok, just to confirm that I understand you current situation. You installed Debian stable (Lenny) and when x starts your monitor complains that the refresh rate is too high, X exits, dropping you into a console?
If the above is correct you should be able to specifically tell X what refresh rate to use by reconfiguring the xserver-xorg package. To do this please run the following command:
dpkg-reconfigure -plow xserver-xorg
If it asks you questions that you don't know the answer to, just leave them blank (or whatever the default is).
xrandr gives me 'Can't open display'
As far as I know xrandr will only work within an x session.