It turns out that if you hunt hard enough, there is a fragment of a wikipedia page that covers this.
First off, what was found was traces of coca and nicotine in hair from Egyptian mummies by one person. Nobody has ever duplicated the coca find (after multiple attempts), but some other folks have found traces of nicotine in some other mummies.
Its worth noting that none of these samples were exactly controlled specimens. For example, the initial mummy tested had its person and its tomb looted multiple times over hundreds of years. The general consensus at the moment seems to be that these results, if accurate (a big if), probably represent some other local source for nicotine.
The alternative of course would be to postulate that there were transatlantic voyages going on between North America and Africa. The problem there is that nobody at that time had any navigation technology capable of that feat (and wouldn't for nearly 3000 years). Transatlantic voyaging isn't just a matter of one piece of knowledge that someone could have found and forgotten. It takes a whole set of interacting technology.
For now, I'd leave it at the "interesting mystery" category. It'll probably get figured out eventually.