I was able to get this achievement today, for the first time. I'm not sure how. Altars that hadn't worked for me in previous playthroughs did work for me this time.
Your theory may well be right: I didn't get the sun/moon information from Alexandar or the Sallow Man.
