You could try an acid bath prior to coating. "Acid free" usually means they added an alkaline chemical to the paper (like calcium carbonate). These don't always react well with the traditional cyanotype formula, in my experience. I haven't experienced yellow staining from it, so it might not address your specific issue, but a quick dip in an acid bath and a thorough wash would at least help to clear some of the excess chemicals used during the paper production process, and might make the paper more suitable for cyanotype printing.
You'll want to research how to acidify papers for cyanotypes. There are a lot of different formulas and methods, and I'm not sure which is best. I use a highly diluted amount of HCl, since I have plenty of that chemical and no other real use for it. But most people use another acid that's less dangerous to work with.