Cannot enable enhanced lookups for this object: SomeCustomObject__c

This turns out to be related to the new "Search Faster by Disabling Search for Some Custom Objects" feature.

New custom objects are documented as not being searchable by default, which would strongly imply they aren't indexed. I know internally that lookups use SOSL, and not being SOSL indexed would certainly be a reason for enhanced lookups to not work.

So if you (er.. me?) want to keep enhanded lookups on these objects you'll need to mark them with an enableSearch element.

I.e. in my metadata I need to change to:

<enableEnhancedLookup>true</enableEnhancedLookup>
<enableSearch>true</enableSearch>

Note that this requires APIv35 in package.xml, so you're realistically forced to upgrade if you want enhanced lookups to work on fresh deployments.