Having put together a few more pages - it is apparent that I must be missing something. I added the category menu module to my store page and marked it to display on everypage. Then when the user is on the shopping cart, or any other page on the site, the category menu links don't work.
I am either being very thick and just have missed some setting which tells the Category menu where to link - otherwise this doesn't work for me - as the design of the site is centered around the product categories being visible at all times.
Any advice would be greatly received - I working against the clock on this one....