While I can appreciate the need for basic troubleshooting, most of this does not apply to a problem that crops up as a result of a software update. For example, here are your specific items and why they don't apply or if they're already done.
1) Restart your iPhone or iPad. - as noted, already done.
2) Check for a Carrier Settings Update by going to Settings > Carrier Settings. - This doesn't exist as noted here but I did however hit the settings screen to see if a pop-up occurs
3) Take out the SIM card and then put it back in. If the SIM card is damaged, or doesn't fit in the SIM tray, contact your carrier. - software update wouldn't dislodge the SIM card. If it works before the update but not after the update a SIM shouldn't be of interest.
4) account and carrier outages - Same thing... a software update won't cause a carrier outage nor will it suddenly cause your account to get shut down. Also, other devices on the same account but still running iOS 8 are uneffected - as was this device on 8.
I'm just going to revert to 8. I live on the road for work and a phone that is unstable for cellular service is just not acceptable. And it's not acceptable for a company to put out an update that has a bug of this significance.