The first time I ever owned a cell phone was when I moved to Japan to teach English in August of 2004. With the help of some friends, I picked out a phone that cost one yen (about one cent Canadian) with a fairly reasonable month plan.
It was a flip phone with one large, very bright color screen on the inside and another smaller screen on the outside. The phone was capable of taking photos and video. Similar to a Blackberry, the phone could also send and recieve emails.
The web browsing capabilities were limited only in that I don't think there was much mobile content out there at that time, most of that which was there was in Japanese too complicated for my limited vocabulary and was otherwise difficult to navigate on such a small screen.
The phone was capable of playing mp3 ringtones. I never investigated whether or not it would work as a music player because I had just upgraded my Panasonic Shockwave Discman (!) for a buggy, Toshiba Gigabeat mp3 player.
The point is that this was one of the cheapest, least complicated phones available in Japan in 2004.
Five years later, it doesn't really surprise me that the iPhone isn't very popular in Japan and that carrying one around would be considered "lame."