I think you could run a search [1] with your API key to see if it's the app or the echonest database that doesn't perform well If the search returns no results for those tested & failed queries, than all we have to do is wait, if not, then there's still room for improvement.

[1] http://developer.echonest.com/docs/v4/song.html#search