What is the exact wording of the message you get? Are you able to work out the model of motherboard the machine has? Even though the seller claims it's stock, the model you mentioned appears to have come originally with a AMD-FX4300 chip which is a 95w CPU, the FX4350 you have is a 125w chip. It wouldn't surprise me if a machine like that has a lower end motherboard that doesn't have sufficient power delivery to power a 125w TDP chip and it's therefore downclocking the CPU.
At any rate, unless the fault was mentioned on the eBay listing, I'd be pushing to return the system since it's clearly not working as it should.