Since ArcMap Projects data "on the fly" why aren't these data sets aligning?

Solved: My map's data frame is in NAD_1927_StatePlane_New_Mexico_East_FIPS_3001. When I added the NAD83 UTM data I had assumed it was spatially accurate "on the fly" not knowing that, as @Vince, pointed out, when using "on the fly" projection for NADCON the transformation must be specified manually. After re-adding the NAD83 UTM data and manually specifying the transformation everything came together nicely.

Do they both have a defined coordinate system? I think this occurs because although Arc can project data on the fly, this does not apply when the data is in two different coordinate systems or datums, such as NAD 1927 vs NAD 1983. You need to apply a transformation. See related. I would recommend choosing a coordinate system and projection, and re-project as necessary. See also for an explanation of how to properly project when your data isn't lining up.