I think we have a TDS2000 in the Singapore office (where I am now). I'll have a look on Monday (also).

You are possibly starting to see the resolution of the AD converter coming in to play. Typically only 8 or 10 bits (i.e. the VGA resolution actually shows less detail with a 10 bit converter).

You mentioned connecting "nothing" to the probe inputs. That will pick up all sorts of noise and junk. You should always have something connected (even if it's tied to the ground clip which will still act as a loop antenna like Ross mentions).

That 1kHz test signal did look a bit noisy to me though.