Ok, we can try something and see if it solves the problem. I can't test the fix myself because I have a LCD screen, so it would be great if you could do this modification, recompile SFML and test it
If you're using SFML 1.6, add the following lines of code after line 476 of src/SFML/Window/Win32/WindowImplWin32.cpp
DEVMODE mode;
mode.dmSize = sizeof(DEVMODE);
EnumDisplaySettings(NULL, ENUM_CURRENT_SETTINGS, &mode);
DevMode.dmDisplayFrequency = mode.dmDisplayFrequency;
DevMode.dmFields |= DM_DISPLAYFREQUENCY;
This will use the current desktop frequency for the new fullscreen mode, instead of relying on the default behaviour of the OS.