The problem was I wasn't converting the operation id (39) to hex.

what encoding are you using and how do you sign your transaction?

I'm encoding the strings with UTF-8 and using my own Java lib for signing.

Thanks for stopping by @bennierex and trying to help a nerd in distress :)