Warsam, I filled out a bug report detailing my struggles with both Catalyst 14.9 and 14.12 autodetecting faulty resolutions from my monitor (Gateway FPD1730). Turns out I needed a custom xorg.conf with the right features:
Modes calculated by cvt
No/commented out HorizSync/VertRefresh lines
PreferredMode
I used the default xorg.conf created by aticonfig --initial and hacked it to do my bidding. Took awhile.
Bottom line is that your Ubuntu driver seems to be getting wildly inaccurate EDID data from some monitors. This problem has been happening for awhile now, since I have seen bug reports/complaints about this problem since Ubuntu 9 or so (if not earlier). The usual 'fix' is to try a different monitor cable or to plug the cable into a different port via an adapter until the driver pulls in some at least marginally-correct settings via autodetect. Otherwise, people generally give up on fglrx and go back to the Radeon driver.
The truly bizarre problem is that, after choosing the wrong resolution, somehow X gets hosed so badly that you can't use xrandr/xset from a command line to fix the problem.
Also, the .deb packages you are hosting on your site have the typical wine incompatibility problem. Fixing this is REALLY easy, all you have to do is, well, this:
http://askubuntu.com/questions/540780/14-10-wine-and-fglrx-conflict
Yeah I know I posted this URL earlier in the thread but big whoop. Just follow the first answer, only in the case of the 14.12 Omega driver, different filenames are in effect.
Regardless, I used those directions with your .deb files in Lubuntu 14.10, and installation was successful despite my having wine installed alongside it. If I encounter any problems in wine that I didn't have when using Gallium .4, I'll be sure to let you guys know . . .