Update with a new proposal for a solution:
What if you started each conversation by asking a customer for the answer to some pass-phrase that only he or she should know? A similar option has been used as an extra measure for a long time at a company I used to work for, where security is relatively high, and I have a hunch it just may help sidestep problems like yours.
The way this works is as follows: When a customer calls and gives his or her name, you look up their info, including a plain-text question and answer set. Now immediately ask them to verify their identity by answering the question, which you read to them.
What would this achieve?
Two things, I would hope: Firstly, it should improve your security, even if only marginally. The information may be stored in plain text, with everyone working at the help desk having access, and it would probably be the case that many of the answers would be easily guessed, especially if an attacker did a little research before calling you. Even so, this should still make it just a little more difficult to impersonate one of your customers over the phone without triggering any suspicion.
Secondly, and more importantly for your particular problem, this should make it clear to the caller that you have in fact identified them, and are looking at their customer data right now. The idea here is that you actually allow your customer to be helpful. That is, after all, probably why they are so eager to give you their passwords, right?
In essence, you will then be providing them with a simple way to identify themselves without disclosing the more sensitive piece of info that is their personal password.
My previous answer:
You can and should keep trying to educate your users about issues like this, but there will always be users who are ignorant of this, or who do not take it seriously. Whenever that happens, make sure to politely inform your users once again about it, and tell them you have a policy that requires them to reset their password now that it has been revealed.
If this is a recurring problem, you might also want to look into why this happens. Do people at your help desk actually require access to customers accounts, even if only for a short period to help them out? Perhaps you can find some solution where temporary access is given with a temporary password? If this includes an advertised solution making it simple for you to help your users, while also obvious for them that you can get access without them having to provide their passwords to you, then perhaps they won't feel the need to "help" you access their accounts?
Obviously this would require logging each time an employee accesses a users account, preferably with a short description of why, and what was done, etc., along with a strict policy concerning confidentiality and guidelines about what employees can and can not do, etc.