This "simple API over a complex problem domain" sounds like "leaky abstractions" - is that what you have in mind? By the way this article describes a similar sentiment I think: Complexity of APIs.

But I don't agree that measuring API complexity is hard - what is hard is judging if the complexity can be reduced without introducing "leaky abstractions", but you can have quite simple measures. By splitting the problem into two - first analysing the functionality and how much of it can be abstracted away - and then measuring the complexity of the API we can make the evaluation of an API more manageable.