I've had that conversation many times. It usually ends like this for me:
"Have you ever heard of an aircraft carrier?"
"Yeah"
"Well... those planes and helicopters are the ones the Navy flies"
"Oh, I thought the Air Force landed on the Navy's ships."
That's not completely unreasonable considering how civilians do not talk about us and think about us on a daily basis. For the uneducated it's makes sense that all planes are the AIR FORCE and all ships are the NAVY, even though each branch has a bit of their own. If people ask, then I'll educate them, but if they're too dense to believe me then it's over.