We describe a spectroscopic survey designed to uncover an estimated ~40 AM CVn stars hiding in the photometric database of the Sloan Digital Sky Survey (SDSS). We have constructed a relatively small sample of about 1500 candidates based on a colour selection, which should contain the majority of all AM CVn binaries while remaining small enough that spectroscopic identification of the full sample is feasible. We present the first new AM CVn star discovered using this strategy, SDSS J080449.49+161624.8, the ultracompact binary nature of which is demonstrated using high-time-resolution spectroscopy obtained at the Magellan telescopes at Las Campanas Observatory, Chile. A kinematic S-wave feature is observed on a period 44.5+/-0.1min, which we propose is the orbital period, although the present data cannot yet exclude its nearest daily aliases. The new AM CVn star shows a peculiar spectrum of broad, single-peaked helium emission lines with unusually strong series of ionised helium, reminiscent of the (intermediate) polars among the hydrogen-rich Cataclysmic Variables. We speculate that SDSS J0804+1616 may be the first magnetic AM CVn star. The accreted material appears to be enriched in nitrogen, to N/O>~10 and N/C>10 by number, indicating CNO-cycle hydrogen burning, but no helium burning, in the prior evolution of the donor star.