The two are almost interchangeable. However, in my mind (and I might be wrong), when you speak with somebody, you are often doing so in private.
Examples:- He spoke to the pope as he passed by.
If you say "he spoke with the pope", this suggests something more private. In fact the expression is likely to be something like: "he spoke with the pope in private".