I just got a 16 tooth and tried to put on the old chain, BUT while it fits on the pedal cog (46 tooth), it does not on the rear cog. How can I solve this? a different cog in the back or a different chain? (on the rear cog, the chain has bigger "holes" than it should, so it doesnt fit...) Thank you so much for any advice...!
You might have bought the wrong width chain. For road bikes/fixie there are two possibilities. These are the width of the chain. 3/32" and 1/8"
a 3/32" chain will not fit on a 1/8" cog but a 1/8" chain will fit on a 3/32" cog (but with extra space around the teeth).
If it is the length of the chain you are talking about then get a new chain. but the pedal cog might also need to be replaced.
More economic route might be buying a used rear cog (be warned this might be unsafe if you end up riding a lot wear will be faster)