1. First off, aggressively clear your browser cache (in chrome speak, "since the beginning of time").
2. Have an administrator verify that the basemap group is set to Esri Default, or to a group that has Esri basemaps in it. (One of you has already).
Other than these two, I can't think of any reason why it wouldn't be working. Searches in arcgis.com (which effectively what getting the basemaps does) have been a little slower due to load. Does it display if you wait a bit?
Mike