It seems unlikely that it has anything to do with interlacing, since the PNG is a full frame and WMV only uses full frames. Can you post a screenshot of the PNG and the result after encoding so we can see what you mean.
Also, please list the settings that you used for your WMV Export. WMV's are compressed (some very heavily), and it could well be that you can improve the result, but likely at the expense of a larger file.
Also, I would look at doing a Save_As from PS, and choosing .PSD, which will not compress this correctly sized image. BTW - sizing in PS is a good move, that too many overlook.
Depending on what your source artwork is (maybe AI Vector?), when you resize, you have several options for Interpolation, depending on your version of PS. Some might yield better results, than others. What Scaling algorithm did you choose, prior to doing the Save_As .PNG? For Video, and depending on the artwork, some will be better, than others.
I found the answer.
When exporting the media in premiere, there's an option "allow interlace processing" that needs to be checked.
It took me a few hours of experiments to find it.
Good news, and thank you for reporting what worked for your logo.