WOW, what an easy fix – Thanks for the KB search Joel!
I run Vista, had CS3, uninstalled CS3 and installed CS4 and immediately had the Media Encoding error when encoding from Premiere. I also saw a “Adobe Dynamic Link error” when I tried to load the adobe sequence from my Premiere project directly from Media Encoder, so this solution makes sense.
I wish all serious bugs were this easy to eliminate.
Jeff