Extending wp_nav_menu for taxonomies using walker

I am starting to put together a website that will have several levels to its main navigation (similar to the main navigation on play.com) and I want to make sure I’m taking the right approach to the template before I proceed!

I have built custom taxonomies for local areas and business types, that works fine. I also understand custom post types. I now want to insert these taxonomies into some of the navigation sub-menus.

The question:
Is the right approach to use wp_nav_menu with an extension of the Walker class? As I see it I can use the Walker class to cycle through pages as required, but in certain sections deviate and loop through taxonomy items in a sub-branch. Example structure below.

e.g.

Areas (page)
 AreaA (area-taxonomy)
  AreaAB (area-taxonomy)
 AreaB (area-taxonomy)
 My City (page)
Businesses (page)
 Register your business (page)
 Businesses (business taxonomy)
  BusinessType1 (business-type taxonomy)
   BusinessType2 (business-type taxonomy)
   BusinessType3 (business-type taxonomy)
  BusinessType4 (business-type taxonomy)
  BusinessType5 (business-type taxonomy)
 New Businesses (page)

As you can see some of the sub-pages will be the roots of taxonomies. Pages would not feature within a taxonomy sub-tree.

(Side note: This is my first ever question, testament to the excellent API, examples and documentation of WordPress. I could never switch to anything else!)