How long is the cable? Sounds like an interference problem which could be due to the cable being too long and/or not being shielded well enough.
From my personal experience this is more likely to occur with VGA cables than it does with DVI/HDMI cables. You never know that is not going to happen with a new cable, chances are rather slim of it happening again though. You could however pay extra attention to the shielding this time.
Don't buy into the 'gold plated' crap, if they used and the price is okay it's fine. If they used it and charge £50 for a single 2m cable they're just making crazy profit margins and you'll have a cable that isn't actually better than the majority of <£10 cables.
[edit]
With a Samsung monitor I've had a flickering image due to the dynamic contrast acting a bit silly after a few years. If your monitor has an option to disable the dynamic contrast ratio you could give that a go.