The problem is that a Margin is really of type "System.Windows.Thickness" which is NOT a dependency object, thus Left, Top, Right, and Bottom are NOT Dependency Properties and thus cannot be animated using DoubleAnimation (which allows for tweening).
What is used to animate the Margin is an ObjectAnimation which does not tween. This is why you see the margin jump from its original location to its new location. As another common example, the same happens when you try to animate the Visibility property between Visible and Collapsed.
You would either need to do timer based animation in order to animate margin or implement your own Animation type for Thickness objects.