This help topic explains the problem you're seeing here: http://help.arcgis.com/en/arcgisexplorer/help/#/Troubleshooting/01560000004p000000/ "This message may also be shown if the service is a WMS service which does not support an appropriate coordinate system to match that of the basemap. In this case, you may be able to create the map using the ArcGIS.com map viewer, and then open the map in Explorer Online." Note that the map created in the map viewer will be using the spatial reference of that WMS service, not the default Web Mercator, so this note in the basemaps help topic will be relevant at that point: http://help.arcgis.com/en/arcgisexplorer/help/#/The_basemap_gallery/01560000001n000000/ "If the spatial reference of the map is not Web Mercator, the basemap gallery will be disabled."
