This error message has broken the heart of many a SharePoint professional trying to set up a search content source for an external content type. This is a difficult one to get to the bottom of when you are under time pressure because there are so many things that can go wrong. Firstly, the database permissions have to be set up correctly. Then you have to set up the external content type. Then you have to set up the search service application correctly, and then figure out which accounts to give access to in the BCS service application (which might also be running on a different farm).
The qualification of the error message in brackets is most commonly "access denied by Business Data Connectivity" which means that the permissions on the BDC are not set correctly. So the key thing here is to make sure that the account used by the crawler is given access to the external content type in the Business Connectivity Services service application. You need to set this up the same way as you do when trying to create a list based on an ECT (another source of the "access denied by Business Data Connectivity" error that is shown above as the corollary to the main error description). You need to go into your Business Data Connectivity Service Application, and set the permissions on the object. First, go to Central Administration->Application Management->Manage service applications. Find your Business Data Connectivity service application and go to the Manage page. Click on the Set Metadata Store button on the ribbon and in the Permissions pop-up dialog page you can add the account and set its permissions. This will set permissions for this instance of the BCS application as a whole. You can also set permissions on individual ECT's by selecting them and using the Set Object Permissions instead, but there is a risk here that you add an external content type later and find you can't crawl it. It is also tricky to set these permissions because there is some cacheing going on in the background that means that it takes about a minute before the changes take effect, so it's a bit like steering an oil tanker.
But which account? Surely that would always be the default content access account, right? Ah, you must be new to SharePoint; guess again. First, while the default access account is specified when you create the Search Service Application, be sure to set the password in the Search Administration page. Click on the link for the default content access account in the System Status section, change the account name if necessary, and enter the password. Search doesn't seem to be using managed accounts so you need to set the password here or again you will get the error even if you have set the permissions correctly in the BCS configuration described above. If you have done this it should work for pass-through authentication (user's identity) or secure store (impersonation) provided you have set appropriate permissions on the back-end database of course. If you didn't do this you will still get the error, but the qualifier will be something like "The SELECT permission was denied..." or "login failed for user domain\account" if the credentials are wrong. With secure store you might see "Cannot open database "Secure_Store_Service_DB"...".
That covers pass-through and impersonation. What about RevertToSelf? The service account used for the BCS or Search service applications? The BDC application pool account? No - for some reason it is using the farm account. Hmmm. If you use RevertToSelf (BDC identity) authentication, then "self" turns out to be the farm account (which means it needs database permissions).
When you have it working, don't forget you need to an index reset and then re-crawl the content to populate the search index.