I think I made a lot of progress today. I'm up to about 33 hours, and I just killed Ninetails. The battle with him scared the shit out of me when I saw that second paintbrush show up O.o but I still prevailed.
One thing that really pissed me off: Without any warning or provocation, the game completely cuts off your ability to travel outside of North Ryoshima, forcing you to make due with whatever supplies and praise you've picked up since then. There is one merchant available, but your ability to upgrade your stats during this time is very limited. If you aren't able to defeat the boss, you better hope you made multiple save files.