It's called interlacing, (well, it sounds like interlacing), which is actually normal in higher picture quality.It's usually more visible when there is motion, and when a clip is slowed down.

http://en.wikipedia.org/wiki/Interlace

Every file exported by Premiere is interlaced, I suggest using Virtual Dub to deinterlace it using a filter. The compression options can also give you great quality files of smaller size.