I don't know if this will help you, but I've had COD as an option along with both Paypal and Paypal Express, and the only problem I had was when Paypal wasn't including the shipping address a few months ago.