I created two different MXDs, one for City of Tucson and another for US States. If you click on the ArcGIS.com Map link above (in the services link page), you will see that City of Tucson Layer is overlaid on the basemap but the US States is projected somewhere in the ocean. I know this is a projection issue but if you look at the metadata in the services link, both are showing Spatial Reference: 102100 (3857).
Now the projection of the City of Tucson is NAD_1983_HARN_StatePlane_Arizona_Central_FIPS_0202_Feet_Intl in the ArcMap and the US States is WGS_1984_Web_Mercator_Auxiliary_Sphere in ArcMap. I tried to change the projection to WGS84 but the layer is still not projected properly.
How can I correct it? By "correct it" I mean that the projection should be like City of Tucson where it is projected properly over the basemap in ArcGIS.com.
UPDATE: Projection Tool used
I used the Project tool in the Projections and Transformations Toolbox, which creates a new Feature Class as per the Co-ordinate system we provide. So the original data had co-ordinate system of WGS_1984_Web_Mercator_Auxiliary_Sphere and the new one I assigned was GCS_WGS_1984. The new output was saved in a new File Geodatabase. The Spatial Reference that is now reflected in the Meta Data is 4326, which is not what I wanted. I wanted it to be same as City of Tucson which was 102100 (3857).