Проблема была решена вчера вечером. Оказывается нужно было поменять базу пермалинков для категорий с shop на что-либо другое, например product-cat, так как shop уже был назначен базой для товаров. Одно и тоже слово в базе пермалинков товаров и категорий не может быть. Спасибо ADv, который помог решить проблему.
