There were cases I met when contamination cannot be eliminated even new GC column was changed. The main suspect is the injector typically when the profile of the contaminants are consistent. This is happening when you are doing splitless, hot on-column (not a right technique after all) or large volume injection techniques and when split vent is almost constantly closed all the time. Moreover, your works are in food or environmental or typically high boiling compound analysis. The main reason is condensation of these high boiled contaminants on cool spots of the injector outside the liner. Immediate cleaning by baking the injector with high temperature and high split flow will help. If persists, solvent cleaning is needed to the injector is highly recommended to be done by the service personnels.