What (I suspect) this book means by "small error rate" is "if we allow for some non-zero probability of failure in the outcome", not "there's some noise in the system".
For example, in Deutsch-Jozsa, you're looking at whether a function with $n$ bits of input is constant or balanced. With a quantum computer, you can determine the outcome with certainly after exactly 1 oracle call. With a classical computer, to guarantee that you can identify the different require $2^{n-1}+1$ calls. But you could run a classical version of the algorithm making (for example) 50 oracle calls. If all answers are the same, you say the function is constant, otherwise you say it's balanced. You can only make a mistake if the function is balanced but you claim it's constant. That happens with a probability $1/2^{49}$ assuming your inputs are randomly distributed. Most people could probably accept this level of failure (or some fixed level of failure), in which case you can use a constant number of oracle calls in the classical case as well. So, in that sense, Deutsch-Jozsa does not allow a change in the scaling.
On the other hand, Bernstein-Vazirani shows a scaling improvement even if you allow the classical algorithm to have some probability of failure. To see this, recall the problem: find the $s$ for which $f(x)=f(x\oplus s)$. The quantum algorithm, again, takes exactly 1 step. On the other hand, imagine we make $k$ samples of the classical oracle. This gives us the opportunity to compare $\binom{k}{2}$ different pairs of strings to see if any make a collision. Each (if everything is selected with sufficient uniformity) has a probability of $1/(2^n-1)$ of finding a collision. Hence, the success probability is no better than
$$
\frac{\binom{k}{2}}{2^n}<\frac{k^2}{2^n}.
$$
For the success probability to not be exponentially small in $n$, you need $k\sim 2^{n/2}$. So, we get this big, exponential, separation between the deterministic quantum algorithm, and the bounded error classical algorithm.
