Since the new Ocean Basemap was added, i have noticed that if it is the default basemap loaded, the zoom levels of the map are then restricted no matter what layer is chosen after that.
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();