I seem to have a unique problem. I know lots of people are having FPS issues with the rx 480. But here is my issue. I recently bought a new computer with an AMD 8350 with 16gb ddr3 and an RX 480 4 GB. All games seem to get around 30 fps regardless. I've tried DDU uninstaller and reinstalled drivers and that did not work. But here's the thing. My old computer I still have. It is an AMD 6350 with a gtx 960 or 970. It runs GTA 5 at 40 to 50 fps on high. When playing both computers on gta 5 side by side they both look the same but with the new rx 480 I can not use the proper screen resolution of 1920 by 1080. Instead, I have to run it at 1914 by 1054 and it uses 2 gb on vram to run that resolution. I think that covers all of it.
Try a clean install of Windows, then fully updating Windows, before installing the latest Crimson drivers.