I used a brand new ale pail just recently and I wasn't able to remove the discoloring left on the inside despite how much I scrubbed. Is this normal/will it affect the flavor of future brews?
Iodine based sanitizers may also stain your plastic equipment.
My recommendation: Leave the bucket outside in the sun for a few hours, then smell the inside. if the inside has any aromas then you need to take the bucket back or get a new one.
You shouldn't scrub plastic - it will scratch it, which leaves small spaces for micro-organisms to grow, which are subsequently even harder to clean away.
Instead, get a cleaner such as PBW or Oxiclean (I personally prefer PBW since it can be reused - Oxiclean loses potency once the oxygen has been released.) You can fill the pail with the made up PBW (4g/liter, ca 3oz/5 gallons) and leave this to soak for half an hour. It will pull of any residue and possibly discoloration also.
If you didn't buy the pail from a reputable homebrew store, it would be wise to check the plastic mark on the bucket and check with the manufacturer if it is food safe. I've had the same buckets for years and they have not discolored.