I was able to fix the issue. I duplicated each product into its existing category, and then disabled or deleted the "old" copies of those products. The "new" copies show up in the drop-downs just fine.

Not sure what caused this. The products that were showing up in the beginning were not newer than the ones that were not showing up. Oh well, at least it is working correctly now.