Have you tried overlaying the latest AIR? Even 3.2 is at RC stage and can be officially used.
How much RAM do you have? If it can't allocate the heap necessary that typically signifies an extreme RAM shortage. I'm just not sure if a JavaVM will use a pagefile if you don't have enough RAM. Someone else more fluent in Java might know.
Easiest fix to try first is simply close any unnecessary apps like browsers and media players. Only have Flash CS5.5 running. See if you can export.
Unfortuntey I couldnt get publishing to work on my machine and had to use a different one. I don't think it could have been a RAM shortage since my machine has 12gb and the one I ended up using to publish had 4gb.
I tried overlaying the latest AIR as sinious suggested, but that only changed my error message by adding the line about ADT as in the original post.
I was finally able to get the app to compile by calling adt from the command line. Here is an example .bat file that worked for me:
@set java_cmd="C:\Program Files\Java\jre6\bin\java.exe"
@set java_param=-Xmx128m -jar
@set adt_cmd="C:\Program Files (x86)\Adobe\Adobe Flash CS5.5\AIR2.6\lib\adt.jar"
@set files=helloworld.swf AppIconsFolder
%java_cmd% %java_param% %adt_cmd% -package -target %target% -storetype pkcs12 -keystore %cert% -storepass %cert_pass% -provisioning-profile %provisioning% %build_file% %desc_files% %files%