I want to upgrade to a new distro because Ubuntu 16.04LTS has MAJOR problems with any graphical use, I can't edit videos, and the screen is really glitchy, I can't watch videos on fullscreen because of this anoying glitchy thing. I would be also happy if someone would suggest a distro. I heard that Ubuntu 14.04 supports AMD graphics. So what should I get?
The newest version of Mint is based on Ubuntu 16.04, so you're not going to have much luck there. I believe most, if not all, current versions of Linux are incompatible with
fglrx (as long as they use Xorg 1.18 or later).
If you want to be sure you can use your card to its full potential, you'll have to find a distro you like that uses a version of Xorg below 1.18. Ubuntu 14.04 will work, and so will any distro based on it.
If you want a more complete explanation and some other options for AMD, look at the link edwinksl provided. I really don't want to rewrite what I wrote there, so you'll have to go look ;).