OK, it's definitely an LMDE problem. I wiped my system and /home partitions (after backing up, of course), and installed a naked (as in - boots to a console) Debian OS. Afterwards, I installed xorg and gnome, followed by fglrx drivers from the repository, and everything is working just fine. The downside is that I've got to spend a lot of time building my system up to what I want again, but at least it works properly again. Everything is up to date from testing, although I have several updates available after adding the multimedia repos, which I won't install until I have a backup to fall back on. If anything breaks after that, it's a step closer to the problem.
ATI's own propriety drivers are still failing, but not such an issue with fglrx from the repo working.
On the negative side, whilst I will continue to help people, I'll become less and less able to offer Mint specific help (though I should be able to continue with more general help for LMDE).
Kernel Linux Tex 3.2.2-1 (64 bit) xfce , burg
ATI Radeon HD 4670, 1GB
AMD Phenom II X4 (965BE) @ 3.6 Ghz (Overclocked)