I think this may be the problem, I read this from esri sample:
You can add additional basemaps to the gallery, however all basemaps added to the BasemapGallery need to be in the same projection. If you are displaying basemaps from ArcGIS.com by setting showArcGISBasemaps = true then the additional basemaps must be in the Web Mercator projection.
So try to change the projection of your map service to "Web Mercator".