So I followed these instructions from an Apple Discussions post and got things working again:
Set Watch Mail Notifications as "Mirror iPhone"
On iPhone set Alerts for each account as "Lock Screen"
On Sounds & Haptics go into "New Mail" and make sure "Vibration" is not set as "None (Default). Pick one.
For the vibration, I just created a custom vibration consisting of a very short single tap and turned that on.
Set Watch Mail Notifications as "Mirror iPhone"
On iPhone set Alerts for each account as "Lock Screen"
On Sounds & Haptics go into "New Mail" and make sure "Vibration" is not set as "None (Default). Pick one.
For the vibration, I just created a custom vibration consisting of a very short single tap and turned that on.