Menu personalizado para cada categoría

Buenos días,

ante todo presentarme ya que es mi primer mensaje en este foro.
Me llamo German, soy de Sevilla y estoy empezando a usar en condiciones wordpress. Antes lo habia utilizado para «salir del paso» pero ahora me estoy dando cuenta realmente de las caracteristicas y el potencial de wordpress. Seguramente me vereis mas por aquí porque ante nada, tengo muchas ganas de aprender.

Mi pregunta es la siguiente:

Tengo un blog de wordpress en la versión 3.2.1 y usando el tema Arras Theme. Quisiera meterle en el slidebar un menú, pero que solo aparezca para ciertas categorías. Me explico un poco mejor.

Es un blog de viajes, y quisiera poder hacer guias de viajes por ciudades. Quiero crear una categoría base por cada ciudad (por ejemplo Madrid) y luego subcategorías tipo transporte, restaurantes, hoteles, etc….y todas esas categorías que aparezcan en un menú lateral, y que aparezcan las subcategorías de cada ciudad, es decir que si selecciono Milán, no me aparezcan las subcategorias de Barcelona.

He intentado hacerlo con el widget Menus que viene por defecto pero me aparece en todas las pantallas el mismo menú.

Hay alguna forma de hacerlo??? supongo que habrá algun plugin, pero estoy un poco perdido.

Gracias de antemano.