I like FLOSS Weekly which is about Free Libre Open Source Software. This is hosted by Leo Laporte and Randal Schwartz along with a guest host (sometimes). It is not exclusively on Linux, but they are a great introduction to a lot of the Open Source software thats available out there.
The Tuxradar Podcast by some editors of Linux Format Magzine is a show recorded every two weeks which includes some news about the Linux and Free Software world, a lot of commenting and discussing and a lot of fun (jokes, challenges) too. The guys don't take themselves too seriously and you shouldn't do either.
While no longer in production, the Linux Reality podcast is an excellent way to improve your understanding of Linux and the concepts surrounding it. The full show is 100 episodes long, and each covers a different part of Linux.