You can find the official statement of the "naturalization" here(Article 5)
as you might already know. Tax payment is not referred here.
Tax payment could be one of the means to prove your five years stay in Japan. If you can prove your stay in other way, it will work. Ask your lawyer about it.