I am pretty new to linux, and I was having the same troubles you are. Luckily I was able to find out how it works using various resources on the web. Now I share my knowledge with you
First of all, to change resolutions when you are already in X windows, hit [CTRL]+[Shift]+[+]. This will change to preconfigured resolution settings.
If you want to change the modes that you can run, and XF86Setup and xf86config will not do it how you want them to, you will have to edit the /etc/X11/XF86config file. Don't worry, it's not very difficult if you know how to use one of the editors (I had a problem with this at first). Open the file and go to the section where it has your video card settings. You will see a section for each color depth. There will be a line that lists a number of resolutions, like this:
"640x480" "800x600" etc.....
There will be a line a little higher that says what your default color depth is, so it is the resolutions for this color depth that you are interested in editing. Basically, use the same syntax as what is already there, but put the resolution that you want to be the default first. Hope this works out for you.
p.s. I use slackware, and the file I need to edit is XF86config. I used to have mandrake, and the file there was XF86config-4 . I'm not sure what file you need to edit in Debian, but it will probably be one of those two. Later.