The Weight of Air?

I was watching one of my favorite TV shows (Myth Busters) and they were trying to show if a football full of helium would fly further than a football full of "air." That was interesting, but what I thought was more interesting was a comment they made about the weight of air.
They said if you were to create a cylinder around the Eiffel tower that the air inside the cylinder would weight more than the Eiffel tower. I found this a very strange statement. What did they mean? If I were to take a scale and place it under the Eiffel tower (not under the metal tower, but under the air) I would think it would weight nothing. So, again, what did they mean? Do they mean to say that is must be compressed, and if so, does that compressed air have a weight? I thought the students of Wenzke World would be able to help me sleep at night, as this question keeps me up... Huh

Thanks,
Sleepless in Columbus