[Tavi]

Hola.
Creo que te puedes ir olvidando de los datos.
Si hubieras hecho una restauración de fábrica desde la misma ROM, es posible que hubieras tenido opciones a desencriptar la información, pero el hecho de meter otra ROM nueva (aunque sea la misma en realidad es nueva) supone que la ID del usuario asociada a las contraseñas de encriptación han perdido su relación, es decir, que para tu sistema Android las contraseñas de cifrado no corresponden ni están asociadas al usuario que ahora los intenta desencriptar.
En Windows, con su cifrado EFS, si cifrabas una unidad y no habías exportado las claves e importado hacia un agente de recuperación de contraseñas, si tenías que reinstalar Windows y habías olvidado desencriptar los datos, cifrados se quedaban para siempre. Sí es verdad que el cifrado EFS (ahora bitlocker va mejor) era una basura y desde Linux podías acceder (controlando claro) a los datos cifrados con EFS, pero Android es un Linux (adaptado y virtualizado claro) y no creo que ni el algoritmo de encriptación ni su implementación en el sistema, estén mal hechos.

Saludos

Edito: Quizá haya una puerta trasera, la mayoría de los sistemas de cifrado (menos los opensource) la tienen, sobre todo en USA ya que lo contrario es ilegal para el gobierno. Para tener opciones podrías ponerte en contacto con Samsung, o quiza los chicos de XDA hayan averiguado algo.