It's only a difference of emphasis and/or style. Both are completely correct, in writing as well as in spoken language. I could come up with another expression that uses "tout" in a similar fashion: "tout betement".
Il s’est bêtement trompé de rue.
Il s’est tout bêtement trompé de rue.
and actually, the second one would be quite similar to:
Il s'est tout simplement trompé de rue.
The first one... might put a bit more emphasis, through "bêtement", on the fact that it was a silly mistake, which IMHO is less the case in "tout bêtement".
Note also, that this construction does not necessarily work with other adverbs.
Quite frankly →
tout franchement franchement
Quite clearly →
tout clairement très clairement