The issue is indeed with the keyframes. Once the animation starts, it looks up the location specified by the keyframe and snaps to that location. There are two things you can do to fix this.

1) As you have already found, offset the keyframes in the graph editor. When you do this, grab only the root joint of the skeleton, and modify its translation curves.

or

2) Group the skeleton, then use this group to offset it.