Its a confusing and very difficult process to get Nakata. But ill tell you.
1. At nara city area, near where the G store is, speak with a guy there. mentions something about the legendary. And says that person is traveling around japan, and heard that he was heading north.
2. Go to Hokkaido city area, at first screen speak with that high school guy at lower right side of the map. Mention about that legendary person no longer at hokkaido, and he on his way to east
3.Go to tokyo train station, nakata is standing right in front of station door, but he has a random chance to show up here, speak with him if u do
4.Go to kyoto at city area, speak with the person at lower left side of inside of the G store. Say something about he saw that legendary person
5.Now go to Osaka, city area east side. There will be a guy randomly show up in front of the white track
6.Go to Tokyo train station again, speak with a girl there, she will mention about a saw a person whos really good at soccer with a passion.
7.Now finally go to Tokyo tower, near where the special training symbol is, Nakata should there for you to recruit. Again, he shows up randomly.
8. You need a team level of 60. Also, if he still refuses your challenge, get about 70 team mates.
9. He is simply the best midfielder. Neo Galaxy, his move, destroys any keeper even 10-20 levels above him!