I had this problem too -- I originally had CS3 installed, the installed CS4 and uninstalled CS3. Things started getting strange when I uninstalled CS3 -- lost my file associations, had this encoder problem and a bunch of other things. Finally I completely UN-installed both CS3 and CS4, deleted everything out of c:\program files\adobe (the uninstaller left lots of DLLs there), and reinstalled CS4 from scratch. Now everything works great, including the encoder.
if you launch AME and then from File>Add Premiere Pro sequence, you choose the Premiere Pro CS4 sequence and add it to AME batch and try to encode, does it work?
I am having the same problem (when I click ctrl-M to open AME for render, then click "start queue" AME goes into hang and eventually states "Not Responding"). I just tried the method above, and when I got the window for selecting the project file to import, the same thing happened (unrecoverable hang). I am running Win 7 64 bit (edit: just remembered this is a Vista machine, all current service packs and updates though), and my machine is 8 core with 12GB Ram and a dedicated vid card, so plenty of power and speed.
Edit: running Premiere CS4.2.1 (AME is CS4, but I can't tell you which one, but it is currently hanging... like most of the time)