This is very frustrating, I would have thought 480W would be more than
enough power - has anyone had similar issues?

As far as I know they lowered the required wattage for the 6800 from 480 down
to 350 minimum. I would think you should have more then enough power also.
Maybe the supply is not putting out 480 watts.