We report deep spectroscopy of 10 planetary nebulae (PNe) in the Andromeda Galaxy (M31) using the 10.4 m Gran Telescopio Canarias (GTC). Our targets reside in different regions of M31, including halo streams and the dwarf satellite M32, and kinematically deviate from the extended disk. The temperature-sensitive [O III] λ4363 line is observed in all PNe. For four PNe, the GTC spectra extend beyond 1 μm, enabling the explicit detection of the [S III] λ6312 and λλ9069, 9531 lines and thus determination of the [S III] temperature. Abundance ratios are derived and generally consistent with AGB model predictions. Our PNe probably all evolved from low-mass (<2 M ⊙) stars, as analyzed with the most up-to-date post-AGB evolutionary models, and their main-sequence ages are mostly ∼2–5 Gyr. Compared to the underlying, smooth, metal-poor halo of M31, our targets are uniformly metal rich ([O/H] ≳ ‑0.4), and seem to resemble the younger population in the stream. We thus speculate that our halo PNe formed in the Giant Stream’s progenitor through extended star formation. Alternatively, they might have formed from the same metal-rich gas as did the outer-disk PNe but were displaced into their present locations as a result of galactic interactions. These interpretations are, although speculative, qualitatively in line with the current picture, as inferred from previous wide-field photometric surveys, that M31's halo is the result of complex interactions and merger processes. The behavior of the N/O of the combined sample of the outer-disk and our halo/substructure PNe signifies that hot bottom burning might actually occur at <3 M ⊙ but careful assessment is needed. Based on observations made with the Gran Telescopio Canarias, installed at the Spanish Observatorio del Roque de los Muchachos of Instituto de Astrofísica de Canarias, in the island of La Palma. The observations presented in this paper are associated with GTC programs #GTC66-16A and #GTC25-16B.