Here is a simplified calculation for an ideal rocket. The classical rocket equation to obtain a change $\Delta v$ in speed is
$$\Delta v = v_\text{e} \ln \frac{m_0}{m_f} $$
where $v_e$ is the exhaust speed, $m_0$ is the initial mass and $m_f$ is the final mass $m_f<m_0$.
If you account for special relativity, you get
$$ \Delta v= c\tanh\left(\frac{v_\text{e}}{c} \ln \frac{m_0}{m_f}\right )$$
where $c$ is the speed of light. For small $v_e\ll c$, both equations are equivalent.
In general, $x>\tanh(x)$ for $x>0$. This means that for a smaller $m_0/m_f$ (less propellant) you get a larger change in speed with the classical equation.
A more detailed calculation would need to include type of rocket, trajectories, acceleration and much more.
Source: Tsiolkovsky rocket equation
A case for the Eridians
Maybe Eridians where not thinking in those terms. They just considered the following itinerary: accelerate the ship to speed $v_0$, turn down the engine, reach planet at constant speed.
If that is the case, maybe they thought they needed a large speed to get to destination fast. But the time needed could be slightly less due to length contraction.
They wanted to reach a distance $L$ at constant speed $v_0$ in a time $t$. Classically $t=L/v_0$, but in special relativity is $t=L\sqrt{1-v_0^2/c^2}/v_0$. That means that for a given speed, the observed time for the occupants of the ship is less than what is expected classically.
Conclusion: maybe Eridians thought they needed a larger speed than what is actually needed.
Disclaimer: I do not know nothing about the book. Yet without a precise itinerary/speeds/acceleration the conundrum is still unsolved. If the trip is as described above maybe you can use the rocket equation and the Eridians paradox holds (they used more than what they needed, see section below), but if the trip is different you need to compare how much fuel you need in comparison to the gain in time.
I am also neglecting the time to accelerate and I probably should account for deceleration in order to land but that is symmetric to the acceleration part. So I guess it is actually twice the fuel but the arguments below should still hold.
Some calculations
Suppose that the Eridians wanted to achieve distance $L=1\;\mathrm{ly}$ in $t=3\;\mathrm{years}$ (as perceived from inside the ship).
Classically they would need $v_0=c/3$, relativistically they need $v_0=c/\sqrt{10}=c/3.16...$.
Putting it into the rocket equation, setting $x=v_e/c \ln m_0/m_f$,we get that classically $x=1/3$, while relativistically $x=\tanh^{-1}(1/\sqrt{10})=0.3272$. Which means that they could have used slightly less fuel if they had accounted for relativity.
Let us write the equation for a given $L/tc$:
Classically
$$x=\frac{L}{tc}$$ while relativistically
$$x= \tanh^{-1}\left[\frac{1}{\sqrt{1+1/(L/tc)^{2}}}\right]\approx \frac{L}{tc}\left[1-\frac{1}{6}\left(\frac{L}{tc}\right)^2\right]$$
The $x$ calculated relativistically is alway smaller than the expected classically. Which means that by actually taking into account time dilation, you always need less fuel! (according to the trip above).
The book was right I guess, (ideal) Eridians were indeed wrong.