I played around some more and got it working by setting the Access Restrictions for each label as follows:
Label A: Visible if Lesson Activity is incomplete.
Label B: Visible if Lesson Activity is complete.
I'm sure I did try this yesterday, but must not have.
Label A: Visible if Lesson Activity is incomplete.
Label B: Visible if Lesson Activity is complete.
I'm sure I did try this yesterday, but must not have.