Several times now I have noticed that a custom external data source connector in Salesforce, even though present on the system, will not appear in the list of types when setting up an external data source.

Even though the org has a valid DataSource.Provider implementation in APEX, setting up a new external data source will not show it in the type picklist. Refreshing the page does not solve this. Perhaps time does, I am not sure, but even after 1 hour of waiting and refreshing, re-saving the APEX classes etc., the custom connector would not appear when I tried this yesterday.

Eventually, in my desperation, I decided to go to the Apex classes page in setup and clicked the "Compile all classes" link. After successfully compiling all classes and going back to the new external data source form, finally my custom connector appeared!

The documentation about custom external data sources can be found here