So... I was under the impression that the RX 480's required a newer kernel than what shipped with 16.04, however, one day while messing around I accidentally booted up the stock 4.4 kernel with the Padoka PPA mesa and not only did the RX 480 work, it works awesome. Games are running amazingly well here... Now, on 4.4.0-57 it works perfectly. But on 4.4.0-59 it doesn't work at all, it just goes back to software.
Anyone know what the deal here is? Every place I look claims it won't work unless I grab a kernel from a later version, but it clearly does with -57...