You are absolutely right. I've had my share of problems with the collision routines on the XNA platformer sample. But I've managed to start from the code as provided in the sample, and modified it a bit until I achieved consistent results in every test scenario I could throw at it.
In particular, the sort of problem I was having was when trying to slide along a wall by moving diagonally against it. Because of the assumption the sample makes in order to resolve collisions based on the smallest axis of displacement, this resulted in the character not being able to move when pushing against a wall in some direction. For instance, using one sign, I would get stuck when hugging the ceiling and trying to move against it from left to right (can't remember the specifics). Switching the sign would solve that situation but a problem would appear in the opposite scenario. Bottom line is that with the provided implementation I couldn't get it to work correctly in all sides and from every direction - it would always fail on at least one case.
So the core of the changes I did were all about starting to handle movement on the X axis independently from movement on the Y axis, on two separate steps. I've written about it before in this answerthis answer so head there for the details.
Here's the cleaned up version of the code: http://pastie.org/3152377
And here's a video of that sample in action: http://www.youtube.com/watch?v=5-D0PGdoDDY
And if I remember correctly, the actual reason for it was something like this: