Q: iPhone 5c update to ios 9.3.1 - iMessage issues

Hi, rbrierley!

Thanks for using the Apple Support Communities. I'm understanding that since updating your iPhone, you've lost your message threads in Messages, and are not getting any notifications when new ones arrive. In addition, on your end messages seem to get stuck sending, even though the other person receives the message. I use Messages every day, so I know being notified is important! I've got some troubleshooting that can be done to help fix any issues. Try these steps below.

1. Restart your iPhone. Press and hold the Sleep/Wake button on the top of the iPhone, then slide to power off when prompted. After the phone fully shuts down, hold the Sleep/Wake button again until you see the Apple logo to power it back on. Have someone send you a message and see if you get a notification.
    
2. Make sure that Do Not Disturb is turned off. If you see a half-moon on the left side of the Status Bar, near your battery, DO Not Disturb is turned on. To turn it off, you can either go into Settings > Do Not Disturb and tap Manual, or swipe up from the bottom of the screen to open Control Center and then tap the half-moon Do Not Disturb icon.
    
3. Double check your Notification settings for Messages. Head into Settings > Notifications > Messages. Make sure "Allow Notifications" is enabled, then choose your Notification options. For example, if you want sounds to play when you receive a message, click sounds and select a tone.
    
4. Reset All Settings. If your Notifications are set the way you'd like them, but you still aren't getting them, the next step I'd recommend is to reset your iPhone's settings. You can do this under Settings > General > Reset > Reset All Settings.
   
   None of your data will be removed from the iPhone during this step, but it will revert your customizable settings (like your alert sounds, wallpaper and display brightness, Date & Time settings, etc) back to their factory defaults. It will also remove saved Wi-Fi networks and passwords, and any APN or VPN settings you've previously used. Doing so will clear out any issues your Notifications settings are having.

Since you've also noticed that your previous Messages history has been removed, restoring from a backup is definitely a good idea, if you have one. There could be a number of reasons for that error you've received, and the articles linked below will take you through some troubleshooting to help, depending on which method you're using.

If you've backed up with iTunes on a computer, use this article:

If your iTunes backup couldn‘t be completed or you can‘t restore from a backup
 

If you've used iCloud to backup your iPhone, use this article:

If iCloud Backup couldn’t be completed or you can’t restore

Have a good day!