I was able to solve the problem by clicking "Merge Live Paint" button on the control panel, as described by the following message:
Result.:
I am happy that the problem went away, but I don't understand why the paths were in an unmerged state in the first place. In any case, I hope this information will help someone else in the future.