I've done quite a bit of research on the difference between Custom Settings and Custom Metadata Types, and I've found that in only a few cases are Custom Settings more useful. Custom Metadata types have a number of advantages that make them the correct choice to implement almost always. A lot of this has already been said, but some things have been added recently, so I thought I'd add my two cents.
Advantages to Custom Metadata:
Most importantly, as stated before, they are Metadata and thus deployable! No more annoying configuration after deployment, which you have to do with Custom Settings. They're also refreshed to sandboxes, so you don't need to create Apex classes to generate your default Custom Setting records.
They have WAY more options than Custom Settings: picklist fields, long text areas (in Spring '17), page layouts, and validation rules (though as of Winter '17 these are not deployable either by change set or by migration tool - weird!)
The beauty that is Metadata Relationships! You can create lookups between Custom Metadata objects. Additionally, you can create an Object Definition lookup - so you're relating Custom Metadata to Standard or Custom Object definitions. Additionally, in Spring '17 you can create a dependent lookup to a Field Definition on that object. (Documentation here)
Custom Settings have the same permission to edit the records and to edit the configuration. Both can be done with the "Configure Application" permission. With Custom Metadata, you can edit the records with "Configure Application" but you require "Author Apex" to edit the configuration.
Custom Metadata types have a lot of additional features specific to developing managed packages. You can configure the visibility and editability of fields an objects both by the org that installs the package and by upgrades to the package.
Reason why you would use custom settings instead:
Hierarchies - Custom metadata types do not purport to replace hierarchy custom settings which allow you to vary values based on users and profiles across the org. These custom settings can also be referenced in formulas, so can be used in formula fields, validation rules, workflow rules, and visualforce. (Documentation here)
Web service credentials - If you’re using test credentials in a sandbox, you don’t have any reason to deploy them to production. More importantly, if you create a sandbox, you don’t want the config for the production versions of your Web Services being created automatically and used by default. However, it is usually best to use Named Credentials for this.
Custom setting records’ values can be edited in code, while custom metadata cannot. If you will need to modify your configuration programmatically for any reason (say you’re creating a config console for the user), custom metadata will not work.
There's also been some discussion about testing here. I have a different approach which I detail in my answer to Unit Test - Creating Custom Metadata.
