Do you have any more info on the paperwork part? I've been putting it off for a few months now and considering just registering in the US first to make things easier with US-based clients.
I didn't actually do the paperwork, so I don't actually know how complicated it was. We're actually incorporated in Chiba, and at that time (Nov 2008), the government office responsible for the paperwork wasn't very busy, so they were happy to help out.
Unless you are fluent in Japanese, you probably will need help from someone else. If you don't have a Japanese cofounder / spouse, probably the best thing is to pay someone to help with it.