NoSuchAlghoritmExeption ocurre cuando no tiene ese algoritmo en el entorno de su dispositivo.

Bueno, la primera pregunta aquí es: ¿por qué necesita ECB ? Tiene un monton de desventajas

¿Has probado el CBC ? Probablemente funcionará en todos los entornos de Android. Mis pasos serían los siguientes:

• Intente usar CBC en lugar de EBC , también tiene PKCS5Padding , Cipher.getInstance("AES/CBC/PKCS7PADDING")
• Verifica si el resultado coincide con tus expectativas
• Revise los documentos y verifique qué algoritmos son compatibles con Cipher
• Encuentre bibliotecas con soporte de algoritmos necesarios

Describa su problema de una manera más detallada, por favor.