I am most puzzled.

My Ubuntu, which worked just fine, suddenly a few months back started insisting on running 800x600 or 640x480.
No other resolutions were available.
I've tried changing the driver (Through 'Additional Drivers', in which I have the following options:
*Using X.org X server
* Using video driver from AMD (...) fglrx-updates (proprietary)
* Using video driver from AMD (...) fglrx (proprietary)

None of those solves the problem: Ubuntu is helplessly stuck in 640x480 after I upgraded from 14.10.

Now. Elsewhere (read: Windows) I'd go for a driver update. But this is Ubuntu, and that's just not how this system rolls.
So... How can I tell the stupid computer what resolutions to run?

Ubuntu 15.04
Radeon 6670
TV (32'') through HDMI as monitor.

Did I mention that the GFX works NQA on Windows with this setup?

Please help!