I'm trying to set up a new custom search but when I try to run it I get told the search does not exist and " Please verify your custom search settings in CiviCRM administrative panel." I can't seem to find said settings though, where are they?
You didn't mention how you were making the Custom Search! Assuming it's in an extension:
1) Look in Joomla's and CiviCRM's logs for more information.
2) Try clearing CiviCRM's cache.
3) Check the extension's file permissions.
4) Did you rename some parts of your extension, i.e. files, object names, after creation? If so, there may be a piece missing... try regenerating the extension from scratch and copying the functionality over.