Softbank, if you ask, will upload all of the address information from your old phone to the Softbank website, where you can download it as a CSV file. First off, you have to do that from the Japanese-language website, so it's not trivial for English readers: go to http://mb.softbank.jp/mb/iphone/sync_memory/ and click on the button near the bottom that says "今すぐ移動する".
This will take you to a login screen. Although I had a printout of the username and password from the Softbank store, that's not the username/password it wants. You should have received a message on your phone which contains the username/password you actually need. Once you enter that, you can download your information as a CSV file.
The basic idea here is a good one: now that you have a CSV file, you can import those contacts to your Address Book application on Mac OS X, and from there you can sync with the iPhone. The problem I encountered is that the file from Softbank is in Shift-JIS character encoding, but the Address Book app on Mac OS X wants UTF-8 encoding. If you try to directly import it, you'll get garbage (or at least, I did).
There are probably some utilities that can convert it (on Windows, I would have used SakuraEdit). But, since I know Python, I just used a tiny python script:
# SAB_20081228.csv should be changed to whatever name you downloaded
# from Softbank
f = codecs.open("SAB_20081228.csv",'r','sjis')
fo = codecs.open("SAB_20081228_utf8.csv",'w','utf8')
Now I could import the converted file to Address Book and I was off and running!
And the App Store is really cool.