I am not using Ubuntu, so I can't vouch that this will work. But here is what I do on my Gentoo laptop w/ nVidia graphics:
There is a program called 'nvidia-settings' that is partnered with the proprietary Nvidia graphics drivers. (There is likely a similarly named packaged under the Ubuntu package manager.) Run this utility program and you get a 2-pane interface, with the left side showing a "tree" of various options:
DFP0 - (Seiko)
What you are interested in is the 'DFP0' (may be named differently if you have multiple displays plugged in) "digital flat panel" setting. Click on that, and the right-hand pane will display some options. On my box there is a checkbox titled, 'Force Full GPU Scaling'--click that ON. Next there is a set of radio-buttons underneath the previous checkbox--you want the one titled 'Aspect Ratio Scaled'.
NOTE: When you change the settings, the screen will blank for a second and return. When you have those selected, QUIT the utility. At this point try running Eschalon again and it should give you a non-stretched display.
Now if you are using ATI graphics, there is an equivalent doo-hickey utility--can't recall the name off the top of my head. If you have Intel GFX, I have no idea how to help, but there is probably a scaling adjust utility as well.
Again though, I haven't ever tried Ubuntu, so I don't know where these utilities might live on your system. You can try doing 'which nvidia-settings' in a terminal window command-line to see if the program is even installed under that name.
Hope this helps.