I’ve been fighting working with SharePoint for about a week and trying to get the Search Service started on my SharePoint Server. The only thing that seemed consistent in all the troubleshooting was that the SharePoint error messages were only slightly more helpful than “An error has occurred”. I ended logging a PSS support call with Microsoft and didn’t get very far for a while. My SharePoint farm consisted of the SharePoint Server and a separate SQL server to host the data and attempting to start the service I would get ‘Could not access the Search administration database. A generic error occurred while trying to access the database to obtain the schema version info.’
There are several other posts out there on updating the version of SharePoint to the latest Service Pack, Installing the latest cumulative update(2598321) and ensuring that the protocols were enabled on the SQL instance. All things I corrected, applied and did not fix the issue. (Note that installing the latest cumulative update DOES require a reboot and may stop SharePoint working until you do reboot – so make sure you install this out of hours.)
Upgrading the database is done with ‘psconfig -cmd upgrade -inplace b2b -force -cmd applicationcontent -install -cmd installfeatures’ After running this command I noticed that the checking the status of the server with (get-spserver servername).NeedsUpdate would work fine on the SQL server, but running against the SQL server from the Sharepoint Server, it would tell me the database needed updating.
On one of my servers, Add/Remove Programs said that the hotfix was not required yet the Admin console on the website said it was. This issue was fixed with a “psconfig -cmd installcheck -noinstallcheck” (Thanks to http://tinyurl.com/7pkrbem)

After starting the service on the sql server instance, we wanted to get the SharePoint Server working as originally intended. After a long time of troubleshooting, our next step was to uninstall the SQL Native Client and reinstall it. As I went to uninstall the Native Client, Add/Remove programs told me the package was not installed. A repair or modify would not work either. Opening Regedit and searching for Native Client under HKey_Classes_Root\installer and deleting this key meant I was then able to reinstall the NativeClient.
We then tried starting the service and this time it worked. The strange thing is that some communications between the SharePoint server and the SQL server were obviously working fine – the database on SQL was created with no problems and SharePoint could see the data – it’s just weird that the initialising/upgrading of the database required the SQL native client but did not give any useful information that pointed to this fact.