Ask the provider to check the file permissions of the newsletter plugin and take a look to newsletter diagnostic panel to see if there are reported problems.
I have the same problem. I checked diagnostic panel, changed permissions, but stil 404 error page. I will send you link to unsubscribe in PM now. And please reply me when you will have time. I hope it will not take long time.