First I would check to see if something in the mail template has been modified or customized. If so, try giving them the unmodified version of the mail template to see if that fixes it.
Second, check to see if there are any 3rd-party apps that are affecting Notes (AV, archiving, phone sync, etc.). Perhaps ones intended to work with Notes that worked fine on a previous version? Try removing or disabling those.
Lastly I would try downgrading the mail template without changing the Notes version.
If all of the above fail, I think you can justify calling support.