I think you need to look at the ordinance the City information line operator is telling you in black and white. Some of these people have no clue about ham radio and most ordinances have exemptions for ham radio.
Rick is correct. I live in Albuquerque too and have a tower (and verticals, and wires in the trees). The city is concerned about accessory structures, not radiating elements. The typical zoning office clerk who answers the phone won't know the difference between a G5RV, Rohn 45 or a 5BTV. Put up whatever antenna you like, and get on with your life. Worry about it when you *do* want to put up some Rohn 45.
What HOA or other deed restrictions you may have in that neighborhood is another story.