What he got wrong was that he thought that it would be a computer that would contain a phone as an app, while what happened is that it's a phone that happens to be a computer. And it wasn't even Apple or Google that showed the way, but Nokia.
And it's pretty funny how it happened. So we had these pocket computers a few years later in the late nineties, the PDAs. Some of them were running an OS called EPOC. But nobody (well, very few people) really wanted a PDA, because why would you? It was clumsy and inconvenient with the stylus and it didn't do much.
However, when they appeared, everybody wanted a mobile phone. Because then you could actually call and talk on the move. And then, almost by accident we had text messages. (Initially created for broadcasting messages from the operator to the users. Because who would want to type messages on a number pad when you can make a call, right?)
So then as these phones became more powerful, they would have more and more complex software. At some point Nokia figures out that they could put an actual PC into a phone that people could nickname "the brick". That's the original Nokia 9000 communicator. It had (I'm just seeing) an intel 386 CPU. It's actually the same year Gates wrote this article, 1996.
Then probably others came up with similar products, but the next one I saw was the Nokia 9210, built on that oldish PDA OS I mentioned above, EPOC. And it already had internet connectivity (although not permanent, you had to manually connect through GPRS), with a browser and email, etc. That's 2001 and I happened to have one (and happened to work at Nokia back then).
And then people started saying that "phones are for making calls" and mobile companies like Ericsson and Sony (besides Nokia) start to roll out smart phones based on an OS called Symbian, that is basically a newer version of EPOC. And these are already what Gates was talking about. They started to have a GPS, a camera, always-on internet connectivity (with 3G), installable software, etc.
Microsoft also tried to enter the market (with various versions of windows mobile/ce/whatnot), well before Apple and Google. What they didn't figure out probably is that they would have to build the phone. Back then there was no other way around. Especially if they wanted to make money. Even Google doesn't make money on selling android for mobile manufacturers. And MS didn't have another business model other than that, I think. Though they could have tried given it away for free, just to dominate the market, like they did with IE. I don't know if they tried that or not. But their OS wasn't that good and making smart phones wasn't that easy back then, so you didn't have a lot of companies doing it, and of course, the market was much-much-much smaller. Because that was still the time when people kept saying that "phones are for making calls". (At least that was something I heard frequently when people saw my phones and learned that I work for Nokia and that I write software for smart phones.)
And then Apple came and they made smart phones sexy. Actually the original iphone was way dumber than a generic Symbian smart phone. Like no MMS and no "push" email and, IIRC, no user installable software. But it had a phenomenal UX. So it actually sold the concept to all those people who used to think that these were actually phones (and thus mainly for making calls). And then people wanted iphones and soon a smart phone (i.e. an iphone or an android phone, because Nokia was done with pretty quickly). And after a while they learned that the smart phone is indeed a PC and can do a lot more than taking pictures and pinch-zooming them or the map.