Your map or layer's spatial reference (coordinate system) is different than the spatial reference required by the ArcGIS Online / Google Maps / Bing Maps tiling scheme. To overlay correctly with ArcGIS Online, Google Maps, or Bing Maps, your web layer must use the same spatial reference system. The spatial reference for the ArcGIS Online / Google Maps / Bing Maps tiling scheme is WGS 1984 Web Mercator (Auxiliary Sphere).
Your web layer, the tiles generated for the cache, and all selected capabilities are in WGS 1984 Web Mercator (Auxiliary Sphere).
Note:
The coordinate system for the original map is not changed. The publishing process only changes the coordinate system for the web layer, then uses this to create tiles for the cached web layer.
Solution
Do nothing. Your web layer uses WGS 1984 Web Mercator (Auxiliary Sphere), and you can overlay your web layer with other services, such as Bing Maps and Google Maps, using WGS 1984 Web Mercator (Auxiliary Sphere).
More information
All tiling schemes are associated with a spatial reference. Your map's spatial reference must match the spatial reference of your tiling scheme for tiles to be created.