Most free podcast android apps are pretty terrible, but PocketCast (paid) is really awesome (at least it have a great UI). I don't even listen to podcast that often, but I bought it without hesitation.

But it's true that there's a problem with podcast, so take my +1.