One approach to workaround this issue is to add a basemap with more zoom levels before creating the basemap gallery. In this snippet the World Topo Map is added so the map will be initialized with more levels: var initBasemap = new esri.layers.ArcGISTiledMapServiceLayer("http://server.arcgisonline.com/ArcGIS/rest/services/World_Topo_Map/MapServer");
map.addLayer(initBasemap);
createBasemapGallery();