You will most likely get Warnings in the event application log for Event ID 1357. The message (cuttting it down to the relevant info):
A database error occurred. Source: .Net SqlClient Data Provider Code: 229 occurred 0 time(s) Description: Error ordinal: 1 Message: The EXECUTE permission was denied on the object 'proc_MSS_CrawlAdmin', database 'DSNet_Search_AdminDB', schema 'dbo'., Class: 14, Number: 229, State: 5 at System.Data.SqlClient.SqlConnection.OnError(SqlException exception, Boolean breakConnection, Action`1 wrapCloseInAction)
at System.Data.SqlClient.TdsParser.ThrowExceptionAndWarning(TdsParserStateObject stateObj,
Go to the SQL Server and check - the Search Service Account probably doesn't have the proper permissions on the Search Databases. In my case, I had ALREADY checked these and they were changed.
In a low risk environment, assign it DBO rights. For high risk, it must have Security Admin and DDL Admin rights. Alternately, you can grant the rights to that account via the Database > Security settings (granting execute to all of the Stored Procecdures).