Camilla Townsend's "Fifth Sun" was a really interesting read in that it brought together a lot of sources of the conquest to tell a more detailed story than I had probably heard before.

When the Spanish showed up, the Aztec's enemies didn't immediately line up to join the anti-Mexica alliance, as some people tend to think. The Spanish weren't seen as gods and worshipped. Pestilence would be a factor later on, but in early days the natives they met were quite healthy. The Spanish weren't seen as foreigners from across the sea or anything special because that wasn't really a concept for the natives. The Spanish were just another funny looking tribe from over the horizon that had showed up to fight for space, much like the Aztec's once had.

The Spanish initially had to fight hostile tribes on their own. There were battles where they had to fight through the night, while they were injured, and against incredible odds. The Spanish, especially the ones from Extremadura, were widely regarded by contemporary Europeans as some of the very best soldiers on the continent. Only after they'd done some hard fighting were they seen as having a chance against the Mexica and worth making alliances with.

So, yes, the Spanish won allies who helped them fight the Mexica, but they needed their guns, steel, and horses to win those allies.