Seems to me like you might have a spoke slightly too long. Didn't you say you just had new rims installed?

Also, yes, most CO2 cartridges have enough in them to fill a road or a MTB tire.