If you have a look at the clubs page for the NW Fencing web site you can see that the entry for Manchester Fencing Club has an image, from its name I would guess that this is the large version, which is set to 325px wide in the category.

If you select the club then the image quality is horrible, looking at the name it would seem to be an expanded version of the x-small image.

I am not sure what I am doing wrong, I have set the image sizes at the category level, I am not overriding these at the item level. Given the amount of space available I am baffled as to why the large or x-large images are being used.

Where should I be looking to fix this?

Check the image size you have set in the category's parameters under Item view settings. This should not be XS but a bigger size than that.

It is set to Xlarge in the item view settings.

I have cleared the browser cache and refreshed the page, just to make sure that I am not getting an old copy. Do I need to clear the server cache as well, or re-upload the images?

Make sure that it inherits its parameters from the right category. You might need to check to the item itself.