We haven't had issues when dealing with US-based clients (granted previous to this we didn't have any clients, so I don't have much to compare it to).

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.