Debian 4.0 will work fine on a 3 year old PC. That's not much older than Debian 4.0 itself.

Seriously, I have Debian 4.0 running on a 1990's vintage 120mhz Pentium. There's no problem.
As for getting higher than 800x600, I'm not familiar with getting dpkg-reconfigure to do everything I want, so I always configure X manually by editing xorg.conf. With older video hardware, I find that the culprit is usually a default color depth of 24--I cut it down to 16 to get higher resolutions. But your computer is only 3 years old, so that really won't be the problem. Most likely, the problem is that Debian 3.1 is very conservative by default; I think 800x600 is the highest resolution it will default to, regardless of your hardware.
Oh--Debian 3.1 doesn't use xorg, so instead of xorg.conf you'd be editing /etc/X11/XF86Config-4. The format of this file is the same as xorg.conf.