If he's having trouble explaining it to people, it's because he's not wording it correctly. And if he's wording it correctly he should use the same, correct, understandable wording to tell us.
The point is pretty cool though, algorithmic compression is pretty awesome, especially when you don't have to conform to any particular end result. A fresh Minecraft world is a 240k jar file used as a decompression tool, and the data is a single integer (the seed). In the end the result is some 9 million times the surface area of the Earth.
However, start modifying that world and the data needed to store it balloons. Make a world that accurately mimics the surface of just Iceland and you're going to be looking at a pretty large file.
Accept a world that's a bit of simplex noise and Brownian motion and let yourself be awed. Make a video of rotating around a fractal made from a simple formula - that looks cool. Try and compress a video of your daughter's first steps and you'll get something significantly larger than an icon. Especially an icon that's at least run-length encoded.
https://www.youtube.com/watch?v=36BPql6Nl_U
That's 128 bytes. You could encode that as a 43 pixel RGB888 image. That's less than 7x7 pixel icon!
Now as Jare mentioned in another comment, this video
http://www.youtube.com/watch?v=jB0vBmiTr6o
contains less bytes than a basic 32-bit 32x32 pixel icon. Some of the whole essence of this demoscene stuff is to work within these constraints(256 bytes, 1024 bytes, 4096 bytes, 64 kbytes, ...) to produce this kind of art. Custom virtual machines, on-fly decompression algorithms and methods, carefully crafted data and ingenious ways of data re-use are the key. It's like black magic.
This sounds so wrong. This sentence makes it sound as if any 3 minutes HD video has smaller filesize than a 32x32 pixel icon. Of course people won't believe you if you use that wording.
I assume what you mean to say is, it is possible to create SOME 3 minute video with music that is smaller than SOME 32x32 pixel icon.
E.g. if you store the 32x32 pixel icon in some XML format that describes every single pixel color component, and the video is plain white with some bleep music :p