We investigate the speed of invasion waves for a single species generated by stochastic short- and/or long-distance colonizations in a time-continuous cellular automaton (CA) model on a two-dimensional homogenous landscape. By simulating the CA models, we demonstrate that stochasticity can dramatically increase the speed of invasion compared to the corresponding deterministic CA model or the corresponding one-dimensional stochastic CA model. To explain this phenomenon, we first develop a mathematical model for the invasion involving only short-distance colonization (i.e., colonization only occurs from the eight adjacent cells), and present several approximation methods for solving the model. Our analyses show that the increased wave speed in the stochastic model is due to irregularity in the shape of the wavefront. Further extension of this model to include long-distance colonization demonstrates that stochasticity influences speeds to even greater extents in this case. Using dimension analysis, we deduced a semi-empirical formula for the speed as a function of three parameters intrinsic to short- and long-distance colonization, which agrees well with simulation results. Based on these results, we discuss how important stochasticity in colonization and spatial dimensionality are in the acceleration of invasion speed.