Magento Search not working
Go to System->Index Management and reindex Catalog Search Index and all indexes that require indexing.
After that I re-indexed the site and then cleared the cache manually via ftp var/cache.
I hope this will solve your problem.