>When I go to the Search menu in the Admin area, it always
>looks the same. The skins don't change.

But does search work there? When you enter some keywords and click "Search", does it produce results?

Could you also check if the url
http://nottellingyou.co.uk/cgi-bin/fatbomb/fatbomb.cgi/?keywords=any+keywords
work?

Do you have access to your server error logs?

Kirill