It could be a number of things that have changed configuration wise in the SMTP server as a result of the upgrade.
as much as I hate to say it because the host has already told you they cant help, they are the ones to be talking to.
a look in the SMTP servers error logs should be able to give some indication of why the email is not being sent.
The server may be refusing to relay the message because of the from address, or the from display name. It may not like the to address. It's impossible to say without looking at the error logs though.
