If you shot interlaced, keep it interlaced. If you shot P, keep it P. YouTube will do the conversion if needed. Do not judge the final quality on a computer monitor, use a properly calibrated CRT monitor to judge quality. Apart from that, it does not really matter for YouTube, since their quality is not good anyway.
I don't know a lot so this is a question instead of a fix.
Could you have used the wrong setting in New Project?
I am just wondering for my future knowledge.
Youtube supports 720p now, and I've seen some videos that look great at that setting. There must be some way that I can use Premiere CS4 to de-interlace video. I could do it in Premiere 1.5 years ago without any trouble. It's hard to think that upgrading the software would make it more difficult to get jobs done.
I don't know if this also applies to AVCHD material, but the deinterlacing algorithms used by Adobe for SD material would only amount to throwing away half your vertical resolution. I would be surprised if that is what you want. Maybe WMV is the better codec for YouTube.
I use wmvHD for YouTube and it is excellent.
It takes quite a while to render with max render qualtiy.