Furthermore, I think I figured out what the trigger for the problem is. One of my saved travel companions had an expired AAdvantage number (they expire if they don't see any activity for some time).

I added my saved companions one at a time until it stopped working, removed that one and it started working again. I know that this number isn't active. I'll report this to AA. Someone needs to fix the logic and add a test...