Conversation isn't impossible, it just takes a bit more work. What I found helpful was to listen to interview programs (in my case, Talk of the Nation with Terry Gross on NPR, earlier, and the WTF podcast, later) to assist me in understanding how the flow of conversation should go. When I'm not particularly interested in what the person I am conversing with is talking about, I'll focus on a point made in the conversation that could branch into something I'm more interested in, and ask them to elaborate on it. That way, it doesn't feel like I'm trying to change the subject, and I still seem engaged, while able to at least feel in control of the conversation.
If someone is talking too fast, or in a way where it is difficult to comprehend what they're saying, it isn't impolite to ask them to repeat themselves. My guess is that most people would rather be asked to repeat something, than to get a distant, monotone, "uh huh," or, "yeah."