A catalog item can be added to multiple categories via the Edit button from the "Categories" related list on the catalog item form itself. However, when the actual category record is opened the catalog item is not shown under the "Catalog Item" related list.
The wrong "Catalog Item" related list is used.
Use the correct related list that displays all catalog items that were linked to a particular category.
The correct one is just named "Catalog Item" and not the "Catalog Item --> Category" (this one only shows catalog items where category is the same as the "Category" field value on the catalog item form).