Ho lo stesso problema, con Soundhound...
Le ho provate tutte, anche contattare lo staff di Soundhound che mi propone le solite cose: cancellare cache e dati applicazione... niente, non si riesce.
Ho la versione donate di Titanium Backup, ma non mi risolve nulla...