On any machines that don't have direct access to the internet, the Premiere Elements initial load took a very long time.
However Adobe does provide some logging to diagnose start-up problems, which can be found under \Users\[username]\AppData\Local\Temp\amt3.log (Windows 7 and above).
The Solution
An analysis of the logs identified a request for "Activating License" and shortly after a "HTTP Request Status code 502" which indicates a bad gateway.
The line after the license activation begins gives us some clues to the solution. "License server is https://activate.adobe.com/servlets/inet_sl/sl_v1_7_rclient (protocol=slcore)"
The easiest way to get rid of the Premiere Elements delay is to simply allow activate.adobe.com:443 to pass directly to the internet. Premiere is smart enough to use the OS proxy, so you may need to add a proxy exclusion to Internet Explorer.
If you have no way of allowing traffic directly out, then some form of proxy server may be your only option.
