Try editing
/etc/X11/xorg.conf with a text editor (you'll need root privileges, so start the editor from console using
sudo editorname where
editorname is the editor of your choice. Once the file is open, scroll down until you find this line:
Section "Screen"
there are first some lines (identifier, device) but scroll down to the
SubSection "Display"
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.