I have a high-quality movie in wmv format (640 x 480 - 4:3 aspect ratio), and I brought it into Premiere CS4 to do some additional editing. I'm on Windows/PC.
I set up everything properly in the initial New Sequence window (frame rate, aspect ratio, movie size, etc.) to match the native file, and everything works fine.
However, when I try to export the movie as an FLV, MP4 or AVI, the final result is always pixelated. Everything else is fine - cropping, audio, frame rate, but the entire movie turns into micro squares as if it were rendered at a low resolution no matter how high the bitrate is. I bumped the bitrate to the maximum in some of my tests, but no success. In fact, one my AVI tests reached more than 2 GB, but with the same pixelated results.
Ironically, when I render the same movie in Windows Movie Maker with just some basic effects, I get a really nice result (sharp high-res image, no pixelation) at a pretty low file size.