The fix was surprisingly easy and funny though. I went to the Screen Resolution adjustment, clicked on the "advanced" link. Open the "Monitor" tab, and unchecked "hide modes that this monitor cannot display". The available modes then changed, and I picked 60Hz as the refresh rate. Things went went from that moment on.
Moral of this story: sometimes you are allowed to force your Windows to do something, especially when it underestimating your expensive hardware :P