Hi Owain,
Can I and should I grab a back up before I delete the plugin? Or will it just have the same issue within the backup?
One thing that has changed since it last worked was we have had an SEO person add all-in-one-seo-pack plugin. Maybe it clashes with your plugin?
Cheers
Ken