This issue pops up when we try to deploy the customMetadata from One Org to another . The process I followed was to retrieve the components from Dev using ANT and then deploy it to QA using ANT. Retrieval of the components worked without any issue, but the name with which the components were retrieved was wrong.
If we observe carefully we do not see the __mdt in the extracted metadata but the deploy method expects the metadata name to have ‘__mdt’
Just ensure to modify the name of the custom metadata to add the ‘__mdt’ to the file name and that should do the trick.
Hope it helps!