Logo in video is fuzzy

I am just starting to play around with Express, specifically video projects. I'm finding that our logo displays very poorly (png). I thought maybe that it was a matter of size, so I re-exported from Illustrator at a bigger size, 2000px width, and it shows up exactly the same. I've also tried directly placing the logo on a slide and the exported video still has the logo with very poor quality. Any ideas?