newsletter email not the right "Unsubscribe" link

I have serious problem with newsletter plugin. I have several users everyday calling me and ask me to put them out of the newsletter list. Well I am trying to tell them that I cannot do that (I hope one day I will be able to edit the newsletter list myself) and I am telling them to go and click the "Unsubscribe" link in the footer of the Newsletter.
Lately my clients say that the link dont work and it gets them to a "page not found 404 page". I tried myself with a test account and I receive the same "404 page not found". I don't know what happened, this plugin used to work great, I mean the unsubscribe link used to work a week ago or something if I remember correct but not anymore. I have already made some test and deactivate all the plugins except of the newsletter but with no luck.

My website is http://www.teachme.gr and the url I get from the newsletter email is the following "http://www.teachme.gr/e-newsletter/unsubscribe/1718/"

I have now juct checked an old newsletter and the url i get when I press the unsubscribe is the following "http://www.teachme.gr/e-newsletter/unsubscribe/933c3aa23c4ab631718/"

Please help!