Am I correct in saying that you tried a bulk CO2 tank and a HPA tank when experiencing the FPS drop? You mention stock class but didn't specify that you were using 12 grams for your test.
If you are using a bulk tank, check that your pin valve isn't being choked off. If using 12 grams, follow cobyrne's advice above.
I can't imagine ambient temperature causing that severe of a drop. I have used a 3.5 oz tank in -10°C and only dropped to 250 fps or so before adjusting my springs.