I have the same issue with magento 2.1

I've also noticed that the ajax request returns POST 400 Bad Request from the url POST https://SITE/rest/default/V1/guest-carts/73e1275fe7e37f8d720f8e516bd9680d/payment-information

debug.log [2016-07-19 03:30:29] main.DEBUG: cache_invalidate: {"method":"POST","url":"https://SITE/rest/default/V1/guest-carts/61f787fc991ff87d979572886b1a37b0/payment-information","invalidateInfo":{"tags":["catalog_product_173","FPC"],"mode":"matchingTag"},"is_exception":false} []

Using paypal through braintree does checkout successfully.

I have the same issue with magento 2.1

I've also noticed that the ajax request returns POST 400 Bad Request from the url POST //SITE/rest/default/V1/guest-carts/73e1275fe7e37f8d720f8e516bd9680d/payment-information

debug.log [2016-07-19 03:30:29] main.DEBUG: cache_invalidate: {"method":"POST","url":"SITE/rest/default/V1/guest-carts/61f787fc991ff87d979572886b1a37b0/payment-information","invalidateInfo":{"tags":["catalog_product_173","FPC"],"mode":"matchingTag"},"is_exception":false} []

Using paypal through braintree does checkout successfully.

EDIT:

I was able to track down my issue to a problem with the upgrade script to 2.1.

Running this SQL Fixed my problem

ALTER TABLE sales_invoice_grid ADD base_grand_total decimal(12,4) AFTER grand_total;

See here for old issue: https://github.com/magento/magento2/issues/5409