I figured it out with the techs from Asus.
Apparently you simply need to try a smaller increment of OC, and make your way up. Which is strange since "sometimes" it does work going form 1333 to 1600 FSB.
I tried 1333 to 1400 it saved properly. And from then on, I haven't had it again not saving. The Asus tech "sorta explained" to me that it's some of the safeguards in the bios that prevent from "major" changes being made. I'm a bit sad that the tech guy didn't seem so sure of himself actually lol.
Hope this helps some other unlucky P5N-D owners