Try editing /etc/X11/xorg.conf
with a text editor (you'll need root privileges, so start the editor from console using sudo editorname
is the editor of your choice. Once the file is open, scroll down until you find this line:
there are first some lines (identifier, device) but scroll down to the
and to the line
Modes "1024x768" "800x600" "640x480"
where there are resolutions configured (you might have other resolutions) just add your favourite to the beginning of the list (as you see, resolutions are typed in quotes, "WIDTHxHEIGHT", separated by a space). Those are the available resolutions and are configured for every color depth; I suggest you add your favourite resolution to every depth (to every Subsection "Display"). The first resolution in the list is used if it's possible and the others can be switched using CTRL-+ and CTRL-- (usually using the numpad + and - signs; this works in most cases). When you're ready, save the file and exit editor, then restart your X (in some cases it works if you press CTRL+ALT+BACKSPACE, in some cases you need to use console and do init 3 && init 2
(ubuntu uses runlevel 3 as the graphical one; if runlevel 2 is also graphical, then you might try 4 or 5 instead of 2), and if everything else fails, you can either kill X or simply reboot. Reboot is not needed, but if you can't get your X down any other way, reboot does it
That should fix the border problem, but read some info about xorg.conf (man pages, google..) to see if you can use some other options too.