It sounds to me like you have maybe told your NLE that the project is progressive when your source is interlaced?

I could imagine if that were the case that it would never deinterlace properly?

I had similar issues with Premiere when I started editing, and the solution I used was to open a second copy of premiere, start an interlaced project in that, and copy and paste the timeline from the old (progressive) project to the new (interlaced) project. The OLE was smart enough to take all the clips from the old project and assemble the clips in the new project.

Before trying this, I would try starting a new project and dropping a clip in it. If you are able to render it out OK you know you are on the path to deinterlaced goodness.

Oh, and BTW, for anyone new to interlacing, this page is really useful. The Bob+Weave deinterlace method detailed gives double frame rate output which is awesome for silky smooth slowmos.