You can also have a residency permit (aka "gaijin card"). But a passport will not do. Same rules apply for getting regular post-paid service.

A few years ago, a little girl was kidnapped, and the perpetrator used a pre-paid cellphone to continually call the parents and the police were frustrated that they had no way of knowing who he was based on the mobile phone number, so they passed this stupid law.

Since the law will still not readily tell them who's calling if they use a payphone, steal a mobile phone, or roam into the country from elsewhere, I'm not quite sure what they accomplished other than reinforcing that Japan can be very foreigner-unfriendly and difficult to deal with at times.