Another thought is making sure you test this from non work computers and different situations to see if you can replicate an error.
We are experiencing the same issue- we aren't getting specific information from our leads but just that the link doesn't work. We've tested our unsubscribe link on a few browsers and mail servers but aren't seeing any issues. Were you ever able to figure this one out?
My hunch is that it's working properly but the user experience on the unsubscribe page (we're using the default right now) leads users to believe that it didn't work. I'm debating sending an operational unsubscribe confirmation email to unsubscribers to erase any doubt. Longer term, the unsubscribe page experience might need adjusting to prevent this perception issue. Hopefully I won't find that there really is an issue...
Our unsubscribe page is hosted by Marketo using a subdomain of our domain (as with landing pages). This page is not secure which may cause issues with some users. The unsubscribe confirmation page is not secure and it's on a Marketo domain rather than our domain. I'm going to send this to support to see what they say.