Все очень просто, раньше тоже долго мучился.
Нужно просто быть чуточку внимательнее.
У Вас есть уже созданное меню которое называется например MyMenu.
Когда Вы создаете меню таксономии на вопрос - какое меню использовать, в открывающемся списке Вы естественно выбираете MyMenu.
Обратите внимание что MyMenu в открывшемся списке - ето не меню, а именно словарь таксономии. Поетому меню и не видно, ссылки не появляются.
Taxonomy Menu создает пункты меню, но пункты не отображаются