I am having the same problem. I just want 1024x768, which I should be able to do easily.
Debian 3.1 testing, xfree86, not x11, I think.
NVidia MX 4000+ 128mb (properly insalled, I'm fairly sure).
Envision 470 19".
I used to get 1024x768 by default, then it fell back to 600x800,
Since our problems are so similar, I though I'd "piggyback" on the same thread, hope you don't mind.