My Logo quality at the head of my shop is really bad. Its only 254x88 and has been optimized for web but no luck. I have tried it as jpg/giff/png but no difference and ideas?

http://www.nilarubia.creators.co.uk/shop/

The jpg image is excessively compressed, - 'over-optimized' if you will .
The image file would be quite small even in full quality, so there is no need to go that far.
Go back to the original, full-quality jpg image and re-save at a higher quality. Your current file size is very small at less than 4 kb. If you let it be 10 or 15 kb, the quality will improve dramatically.