The NEC N2002, the latest model for NTT DoCoMo's 3G FOMA service, was rolled out a week ago. Since then, a software bug has been found in 1,500 of the handsets.
The bug can delete data from some functions when certain sites are accessed, according to a statement from NTT DoCoMo.
Sales of the handsets have been temporarily suspended and the company will start exchanging and reselling revised handsets from 1 December.
As mobile handsets become more sophisticated, software glitches have become one of the biggest problems faced by handset makers. NTT DoCoMo recalled several handset models manufactured by Sony and Matsushita for its older mobile phone network earlier this year.
This is the first time handsets manufactured by NEC have been recalled this year, NTT DoCoMo said.