I had the similar problem earlier but I was able to change the resolution using the XRANDR command from the command line interface. When I was happy with the setting I made a shell script to run at startup. This was my resolution used to change to what I set in the script.
Check out this post in Ubuntu Geek for changing the resolution via
command line
http://www.ubuntugeek.com/how-change-display-resolution-settings-using-xrandr.html
Once you manage to find the resolution that you are happy with (using the XRANDR) you can create a script (see shell scripting) and place it in one of your folders. You can then use Sudo chmod +x <filename> to make the file executable. After that go to start up applications and set this file to run at start up.
A shell script is pretty simple. All you'll need to do is create a
file with the first line as #!/bin/sh or #!/bin/bash (depending on
your profile) then the following lines would be what you typed in to
the terminal to achieve the resolution you wanted. Each command will
have to be placed on a new line. Save the file and make it executable
as mentioned above.