Surprisingly, I haven't found anything impressive from him beside this single performance. His earlier works are quite silly, maybe he's changing the style?
P.S. Your link doesn't work ("Service Unavailable"). This direct link to mp3 download works for me. The interview starts with this quite hilarious performance, where he sings a sceptic's challenge.
I'm sure many of you have already seen this performance. Tim Minchin's beat poem "Storm" is about the sceptical, secular understanding of the world, stupidity of quackery and supernatural, weight of dishonesty, and joy in the merely real. Contains strong language.