From my limited experience as a NIN (only lvl 37) Utsusemi alone was enough to get skill, but if you use enf ninjutsu you'll get skill faster.
The advantage about a high skill is less resists but more importantly less interruption rate, if you are soloing or tanking that can be very helpful for times when you need to get those shadows up.
Like I said in another thread, with high Ninjutsu skill, Aquaveil and Nikkariaoe (lvl 30) I never got interrupted. But I was soloing as /RDM to 37 and not many people does that.
