Hi Cameio,
Location helps, Alberta is definitely experiencing freezing temperatures during the cold season, that’s when such problems usually occur. Also, I don’t think that over-insulating would be an issue in this situation.
Assuming that:
In cold climates covering of the ceiling framing members sometimes helps to prevent dark ceiling stains from appearing. Therefore, if you have a single layer of batt insulation placed between the ceiling joists, and narrow, open spaces above the joists, this could be responsible for the stains. Blown in type insulation or dual layer of batts (second layer installed perpendicular to the joists usually prevents stains from appearing).
Please let me know if you have further questions, just click "comment" below.