He wasn't talking about chemical stability (both gasses are equal in chemical stability at shirtsleeve temperatures) but physical stability. Ask any paintballer, and he'll tell you there's a significant difference.
The behaviour of nitrogen gas is more predictable than that of CO2, but with the uses we are putting it to, there is little to no difference. Since we are just inflating tyres and occasionally running light air tools, we can assume that CO2 will behave the way we want it to. If I were going to do more - or run rather more air tools - I'd probably go with a full nitrogen setup, but another advantage of CO2 is it can be had from welding supply, paintball pro shop, or any carbonics/soft drink supply house - which makes it a good deal more available (not all paintball houses have nitrogen tanks.)
The problem with CO2 is that it is considered "cryogenic" - in this case, simply because it is stored under enough pressure to make it a liquid at room temperature. Sustained use - especially at large volumes - will cause a loss of pressure and can actually freeze valving, requiring that the system actually thaw out.
This is caused by the fact that CO2 is stored as a liquid at room temperature, and this is what generates your working pressure source (of 1500-1800psi in the tank.) As you use gas, more evapourates from the liquid stage to fill the depleted volume. As this happens, heat is used to "flash" the liquid into a usable gas, and this is why your tank and valves will get cold. Humidity in the air will condense into the valve workings, and it can and will get cold enough to freeze. This isn't much of a problem (unless your valve freezes open,) since you just let it sit idle until it deices.
If you think you are going to use a lot of gas at once, or you will have sustained use of air tools, you are really better off with a nitrogen setup (since air-tool oil can get cold enough for tools to bind as well.) If you are going to use it occasionally, or just use it for tyres, it will work well as long as you remember to keep an eye on tank temperature (if it gets cold, check your tyre pressure again after you have been on the road for a half-hour or so.)
Another nice thing about CO2 is that you can readily check how full your tank is - just dunk it in warm water (or something similar in a pinch) and see where the condensation line settles. This won't cause any real trouble with tank pressure or anything like that, and will not cause any trouble with a pressure bottle in serviceable condition.
Don't forget to have your bottle hydro-tested every five years, if it's capacity is over a pound. As long as it isn't being whacked around, and is protected from large flying objects, it shouldn't wear out.
In case you are wondering - yes, I am a paintballer as well, and I use a LOT of CO2 (makes nice portable shop air as well, and I know target shooters who use CO2 blasts to cool rifle barrels between shot strings...)
5-90