Chris,
You are experiencing two problems. One is with the ArcGISConnectionBin.exe You have successfully worked around the issues by un-checking "Automatically detect settings" as Erin Brimhall correctly suggests. In some cases this does not work. If this is the case for anyone else reading this, you can rename the ArcGISConnectionBin.exe (located in Explorer (x86)\bin) to disable it. ArcGIS Explorer Desktop will continue to work without the ArcGISConnectionBin.exe in play.
For the Second problem, ArcGIS Explorer Desktop no longer showing Base Maps, Layers in the galleries or a default map when clicking new map.
this was due to an update to ArcGIS online, that changed how content is presented to users based on region. When not signed in IP Address is used to determine region. To work around this there are a couple things that you can do. One is to create your own base maps, as you have done. All ArcGIS Explorer Desktop maps, default map and basemaps are available online and can be found here
http://www.arcgis.com/home/search.html?q=owner:esri_arcgisexplorer
Another workaround is to Create an ArcGIS online account or use one that you have.
https://www.arcgis.com/home/signin.html A public account will work fine for this workaround.
Sign in and then edit your your user profile (or set it when you create your account).
Set your Region to World
Then when using ArcGIS Explorer, Sign in using your ArcGIS online account.
When you are signed in and your User Profile Region is set to "World" ArcGIS Explorer Desktop will show the base maps. Other non-USA regions may also show base maps, which would explain variations in how Explorer users experience this "missing base maps" issue.
Both of these issue will be addressed for the next ArcGIS Explorer Desktop update...
Mark