Pocket Gamer reports that a "development source" told the site that Nintendo and Nokia worked on a "skunkworks" phone project in the early 2000s. The two companies collaborated on R&D for a proposed phone-console hybrid, before the release of the N-Gage, and while Nintendo was apparently doing early research for the DS.
The project was ongoing until it was shown to the Nintendo board of directors, who rejected it. "You have to remember Nintendo is a very conservative company," the anonymous developer told Pocket Gamer. "It always has various R&D projects on the go, but most of them are eventually rejected. It's just how it operates." Conservative, maybe, but to even consider supplementing or supplanting the Game Boy line with a cell phone back then is a bit out there. Consider Sony Ericsson, who are reportedly working on a PlayStation phone this year.
In any case, if the research went on to inform Nokia's development of the N-Gage, it would seem Nintendo made the right call in just making the DS instead.