I work at Braintree.
Generally, this error indicates you've either used the wrong key, or you've somehow modified the encrypted strings before sending them to us.
Your javascript should look something like:
var braintree = Braintree.create("MIIB...")
where the string is your client-side encryption key, which is very long -- much longer than your merchant id, public key, and private key.
If you include your code, both client-side javascript and server-side Java, I might be able to spot the specific issue you're having. Please don't include your private key if you add your server side code.