Ok, I installed 13.9 again and immediately started having problems in FSX. This time it didn't crash to desktop when clicking the menus, but when you try to change to another airplane or change the time/season, the screen goes black and you hear the airplane sound and the only thing you can do is go to the task manager and quit FSX.
So, I got the atiumdag.dll file from the old 13.5 BETA 2 drivers I had before and placed it inside the FSX folder and it works! No more errors, everything works as if it was 13.5 and I have the latest AMD drivers and, if they don't fix this issue, this should be a workaround for future AMD driver releases.
The dll version I'm using is: 9.14.10.0968
I have also reported the issue to AMD and hope they fix it in the next release.