OK that was different information than was in the file... I updated the file and removed the encoding as paypal suggested, but unfortunately we get the same result. We will have to go back to paypal's support to have them investigate. The good news is that it should be working for most addresses again. It is something about that address that doesn't work.