Thank you for pointing me towards the flow traces. I could see that my NAT policy was in fact working, but the firewall policy was not.
I removed the firewall policy and recreated it. It then began passing traffic correctly. I'm still unsure of why it was not working, but recreating it fixed the issue.
Thanks for all of your help!