Figured it out, though this is the lamest solution ever: I hooked into wp_footer instead of template_redirect. If anyone has a better solution or place to hook in I’d love to hear about it – thanks!
EDIT:
That wasn’t the fix I thought it was. Turned out I was writing the function poorly, and did need to be using template_redirect. See Cannot get redirect working