Step 1: Check your junk mail. You will HATE yourself if you don't and that's where it is.
Step 2: Make sure your site can send emails. Fill out a webform, use the Send Test Email, anything, with your own email of course, to see if it works.
Joomla 3.5.1 did change a few things, as mentioned above. I've had to change SMTP ports on a few different sites just to get email going through again after updating. It's also possible your host made some server changes that are now blocking your current settings.
Step 3: If you can get an email through, the next thing to check is all your config - yes there is the one in the user options, but there is also a toggle inside the user itself and the default is set to NO. Third, in Global config there is the option for "Disable Mass Mail" (and send mail should be on of course - made that mistake before!!).
Step 4: Everything is set up right but it's still not working? Go to your plugins and order them backwards by ID. Disable everything you've added to the site that's not there natively (it'll be at the top).
Once you've got everything new disabled (hopefully you don't have so many that you can't keep track of them mentally, but be sure to keep a record if needed), try sending your mail again. If it doesn't work, flip all your plugins back on, they're not the cause. If the email does work, flip your plugins back on in chunks and keep testing until you eliminate the problem. Then you'll at least know what plugin is the culprit and can check the developer page for information.
Step 5: If none of this has worked...check your junk mail again. It might have worked and you just didn't notice.
Step 6: Update all the things and try steps 2 and 3 again. Note that 3.6.2 has the same problems that 3.5.1 has, so you might need to play around with some port settings.
If none of this works, go back to the host. See if they're blocking mass mail, or have heard of this happening on their server. They might be able to help.