I had the same problem. Open the Catalyst Control Center. Then select "Scaling Options", then set "Overscan" to 0%. That solved my problem.
This pointed me on the right direction.
Had a hard time finding that option: it's under "Desktops & Displays", select the desired display on the bottom, right click, and select Configure, and then we have a "Scaling Options" button on the top.
Setting to 0 would make the desktop too big but you can customize it to fit your monitor.
Funny note: now the size fits as should but that option is disabled. No idea... Might be because I changed the "Pixel Format" to PC Standard.