...no matter how beefy you make an aluminum part, after enough cyclic stresses it will suffer fatigue failure.
You realize that chart has a log scale, right? It is not a matter of designing for infinite life, it is a matter of designing for "infinite enough". This is how they make aluminum engine blocks and heads. Sure it will fail in fatigue eventually. But after 50 years or so, it is time to replace the dern thing anyway. In other words, fatigue strength is just one more variable to design around. Even if the part was made from titanium or steel, they still might make the decision to not design for "infinite" life due to other overriding design considerations. Weight, for example.
The concern with the wheel design was not fatigue itself, but rather a higher peak load during the fatigue cycle. The wheels were not designed for the type of terrain they landed on. More bad luck than bad planning because the type of terrain they landed on had not been observed on Mars before.
In my experience, it is very difficult to successfully design for conditions that have never been observed before.