Do you see something like:
PicassoIV:1024x768(16M, 60Hz, 48kHz) ?
There will probably be a bunch of these lines for the different modes. It's the value with "Hz" that is interesting, if that is above or below what your monitor can handle, the mode isn't going to be displayed.
You could basically delete all modes except the flicker fixer modes and a couple of the 1280x1024 modes from the list, if it's bothering you that there are so many, but it's not necessary.
In any case you can go on to the last screen with Continue, you'll then be able to select any of the modes in the drop-down menu and change the refresh rate setting. Once it's set to something that the monitor can handle, you can test that it definitely works by testing "Test computed display settings". If you see an image with the offending monitor, you can save the changes, if not, press space or some other key to get back into the editor.
There shouldn't be much cable swapping once you get at least one mode working and set Workbench to use that.
Oh, and "PAL ... 49Hz" would explain why that doesn't work; it's clearly out of bounds for your monitor (56-76Hz).