User stories—how do I validate them with actual research?

My PM has a list of user stories. We want to find out if they're "true"—basically, if these user stories have evidence to support them, or not.

We're already pulling usage data. I'm also going to talk to our customer support team to glean through customer support tickets/notes from customer support calls (to see if our customers have, in fact, expressed a need for our new feature).

Have any of you used interviews to validate (or refute) user stories? If you have, how have you conducted a good interview without asking leading questions? (or worse, the very unhelpful "Would you use this feature?")

Other qualitative methods to research user stories?

Ideas?