Originally Posted by Advent

Your soldering iron is too hot. Oxidation happens faster at higher heat and you're burning the flux, preventing it from doing its job. I'm assuming your iron has an adjustable temperature because you said you use it on full. Set your iron for 550˚F to 600˚F (290˚C to 320˚C).