Every time I've tried to install Linux, the max resolution is always listed at 800x600. I finally discovered on XFree86's website that there is a special driver called "radeon" which is separate from their main "ati" driver apparently (Link: http://xfree86.org/current/RELNOTES3.html#14). In dpkg-reconfigure xserver-xfree86, only the ati driver is listed, so naturally I would always choose that. In order to get to to work correctly, I had to manually go into the config file and change the driver to radeon and add the 1024x768 modes which solved my problem.

Why isn't "radeon" a choice from the dkpg-reconfigure wizard? On that page above, it's not listed as a separate driver name, but apparently it's different enough to get it's own explanation (out to the side of ati) and to have some cards not be able to use the standard ati one.