The lethargy caused by haste is not paralyzed or restrained, but a different condition. It is a lesser "condition" that could be considered to be along the same axis as paralyzed or restrained.
One way of reading freedom of movement is that letter conditions should be included. A spell or magical effect that half-paralyzes a creature (they are unsable to use one hand, say) would be included, even if it doesn't ues the paralyzed word.
Another way of reading it is that paralyzed, restrained and speed reduction are specific kinds of effects, and lethargy from haste is a different kind of effect with some overlapping elements. Here, a spell that "prevented you from moving your hand" would ignore freedom of movement, but a spell that stated it "paralyzed your hand" would be ignored by freedom of movement.
A final way would be that only things that match the wording exactly would be impacted by freedom of movement. A spell that "paralyzed your hand" would ignore freedom of movement in this case.
We can go further. 2 or more levels of exhaustion, for example, can reduce your speed. Would a magical effect that imposed exhaustion be blocked by freedom of movement? Would it only be blocked if the character we going from 1 to 2 levels, or 4 to 5 levels, and otherwise be ignored? Would the exhaustion still occur, but the speed reduction be ignored, so long as the levels caused by magic brought you over either the 2 or 5 tier threshold?
Or would a spell causing exhaustion, because it doesn't directly cause paralyzed, restrained or directly reduce speed, work and ignore freedom of movement entirely?
I bring up this thought experiment not to answer it, but to point out that there are lots of reasonable ways to handle the situation of a spell that caused exhaustion. And the lethargy of haste looks like an effect similar to exhaustion, more than the effects that freedom of movement blocks.
Then we have the fact that Haste causes this effect as part of the spell ending. You could view the lethargy as something the Haste spell blocks, and the ending of the spell causes your tired brain and muscles to have to recover once the magic was gone. Then freedom of movement wouldn't apply regardless.
We can combine these two, and look at Tenser's Transformation, which when it ends forces a DC 15 constitution save or you get a level of exhaustion. Would freedom of movement prevent that exhaustion if you had 1 or 4 levels before the spell ends?
I don't know, and I don't think anyone should claim to know, outside of their own game that they are DMing in. And the DM should pay attention to if it would cause problems in the game or not, and how they tend to rule magic in their game.
Myself, I'd consider the Haste ending lethargy to be closer to exhaustion, and I'd probably block the speed reduction, but not the action removal. Similarly, magically caused exhaustion wouldn't reduce your speed, but would otherwise do everything exhaustion does, while freedom of movement is up.
But I wouldn't impose that logic on any other DM, nor would I expect any DM I played under to use exactly those rulings. I might propose it as a reasonable compromise between the two extremes (freedom of movement does nothing/haste lethargy does nothing).