I've played a few games of SoBH with my daughters (8 and 11) and they have picked up the game really quickly, and started to get the tactics quickly. I too am surprised at the depth in the game - it seems simple on the surface, but there are enough factors involved to keep things interesting.
I think SoBH encourages you to build your own war band - their are lots of example stats given, but its easy to change things to how you would like them to be.