делал на основе news - добавлял свойства и делал фильтр по ним, можно и что-то типа корзины подключить... Это здесь:
http://skladsistem.ru/
Ну а меню категорий в news имеется. Сложности возникают при связке всего этого - ну это нормально.
Что касается мультикатегорийности - какие проблемы, делайте несколько категорий и соотнисите с ними записи (каждой записи можно задать несколько категорий), а в меню категорий можно задать, какое дерево категорий будет отображать это меню... Кроме того, это похоже на соотнесение с тегами. Вообщем думать надо.
Еще одна сложность - настройка ЧПУ при этом, поведение меню при фильтрации, хлебных крошек, кеширования страницы (фильтрация не работает на закешированной странице) ну и так далее...