This isn't a problem for evolutionary theory. It's literally a necessary prediction of it. Most recent common ancestor of humans and chimps is 5-10 million years ago. Since we have observed tool usage in modern chimps and lots of very complicated tool use in humans, the necessary prediction is that some amount of tool use goes back at least ~5-10 million years, with increased complexity roughly tracking with the continuous increase in braincase size.