Logon to your Server console and run phpAdmin and MySQLAdmin if you have them and look for errors. You can also reindex the databases which might correct the issue.
Do you have a specific example of failed query?
1. By default the search must be 4 characters or longer.
2. The search term can not be one of the reserved words of MySQL
Reserved Words in MySQL 5.0
