I don't think that freedom of movement is supposed to make you immune to paralysis; it's not specifically mentioned, and I personally would not include it under the heading of "magic which usually impedes movement", though I see how other DMs might disagree.
From the SRD:
"This spell enables you or a creature you touch to move and attack normally for the duration of the spell, even under the influence of magic that usually impedes movement, such as paralysis, solid fog, slow, and web. All combat maneuver checks made to grapple the target automatically fail. The subject automatically succeeds on any combat maneuver checks and Escape Artist checks made to escape a grapple or a pin."
It doesn't necessitate that the paralysis be magical, and there is precedent with a ring of freedom of movement in a recent adventure path preventing paralysis while worn.
I can see the confusion, though, especially with the early misconception in the forums about the paralysis being prevented by the life bubble.