Well, you have to look at it from their side - they are forbidden by law from divulging confidential information about a debt to anyone other than the person owing the debt, without that persons express consent. Doing so places them at risk of liability, so they need to ensure they are speaking with the debtor and not someone else. Do you have a better way of ensuring them that you are who you say you are?
If still uncomfortable, you could alternatively, offer to verify only the last four of your social rather than the entire number - they may or may not accept that.
