Found out I had a 3rd party extension that was inadvertently hiding one of the fields in my billing/shipping address (specifically the state/region field). Something was applying a style upon page load that added "display:none;" to the field. Haven't figured out why it is being hidden yet but it definitely is supposed to be there. I don't have any extension that intentionally hides fields in my checkout and I was unable to narrow it down with Chrome's timeline tool.
I stumbled across this solution that ultimately led me to check all of my fields: Paypal Express Checkout redirects to cart for United StatesPaypal Express Checkout redirects to cart for United States
PayPal of course doesn't even list that it is missing field data in the logs. Typical.