The symptoms are pretty obvious: even if the iron was underpowered, melting a thin piece of solder wire should be pretty much instant. My issue has just always been getting the tip to a shiny solder finish with all the recommended tools...just doesn't work once that iron layer oxidizes initially.
EDIT: Although thinking about this now, actually the way you get rid of mill-scale is with white vinegar so maybe that's my actual answer: white vinegar for a couple hours, then rosin flux and then into the solder bath. Hopefully won't remove the entire iron coating on the tip since otherwise...copper tips again.