That is correct: when the 1D particle is going faster, the energy width $\Delta E$ corresponds to a smaller slice $\Delta p$ in momentum, and so the shell takes up less area in phase space.
Remember that ensembles are just probability distributions. The variable $E_0$ here is how accurately you know the energy of the particle. If $E_0$ is a constant (for some reason), then for faster states you really do know the state more accurately and there is a smaller information entropy.
The confusion in this case comes your expectations from the normal thermodynamic entropy. What's important is this: the microcanonical ensemble does not have a well defined and normally functioning notion of temperature.
In fact the system you just mentioned is one of the classic demonstrations of why the microcanonical ensemble does not correspond well with thermodynamics, breaking down in the case of few degrees of freedom (Gibbs, who coined the term "microcanonical ensemble" in 1902, noticed this problem in the very same book).
It's worth noting there is an alternative entropy you can define which is the "volume entropy", counting all states below energy $E$. This obviously does not correspond to information entropy since it doesn't depend on $E_0$. However, this entropy does strictly increase with $E$. With volume entropy you do recover some equations which look like thermodynamics, however it has some other problems (see also Gibbs link above).
If you want a valid temperature, you have to use the canonical ensemble, and lo and behold, one finds the entropy and temperature increase with energy in this case. The energy you get is simply $kT/2$.