It's not unusual to have one test match two different people that you both know. (You should see how many of us match each other here on the forums!)
My maternal grandmother and my father have over 100 matches in common. They don't share any DNA (per GEDmatch). They do both have deep colonial roots, though, with known ancestors in the same areas.
Do you and your wife have any similarity in your ancestors' locations over the past 10 generations?