[General Questions and Answers] Droidriven:
I don't know what you got rid of but it seems to me that when you debloated you uninstalled/disabled something that your messaging app needed. Without knowing what that needed app/service was, there is no answering your question.

You're gonna have to use trial and error to not only install each the apps you removed that might have anything to do with messaging or other service associated to messaging, you'll have to also push it to system correctly so that it has the proper permissions for a system app.

Find a list of the Pre-installed apps your device came with, identify the apps you removed from that list and then start replacing them until you find the one that makes the messaging app work again, when you find the one that corrects it you can go back remove the other replaced apps and keep the app that fixed messaging. Remember to boot to recovery and wipe dalvik/ART and wipe cache partition(do not factory reset) after replacing each app so that it properly starts the app. Replace an app, boot to recovery, wipe, reboot, try messaging, if nothing, replace another app on the list, boot to recovery, wipe, reboot, try messenger, if nothing, replace another app and so on.

To get the apps you need to replace, extract them from your stock firmware if you can download it from somewhere.

Install the apps with a file manager on the device then convert them to system apps or you can adb push them to system.

If you've disabled apps just enable them one at a time until messaging works.

It may even be a combination of things you've removed, that would require more trial and error.

Simple answer I'd the easiest solution would be to flash stock firmware then root the device again and just be smarter about what you remove this time.

There is a correct way to debloat without causing issues.

Before you remove an app, make a backup of it, then remove it, just it, no others, then reboot, if you have no issues then it was safe, do it again with another app, back up the app, remove it, reboot, test for issues. If no issues, keep going with the same steps.

If you do cause an issue, reinstall the app, convert to system app, reboot to recovery and wipe dalvik/ART and wipe cache(again, no factory reset), reboot, continue the removal steps with a different app, etc..

---------- Post added at 10:35 PM ---------- Previous post was at 10:27 PM ----------

Flashify works on lollipop and marshmallow.

But if you have a locked bootloader then you're out of luck on having a custom recovery.

You'll have to find a stock recovery.img for your device to flash with flashify or you can use adb to dd your stock recovery.img to your recovery partition or you can use the terminal emulator app on the device to dd your stock recovery.img to your recovery partition. You'll have to use the exact correct dd command or you'll brick the device. Do a google search to find the correct dd command and recovery partition location for your model number. Make sure you're certain of the command before you do it.

You may can flash the stock recovery.img(rename it to recovery.img if you have to, changing the name makes it work correctly with the fastboot command) via Fastboot using this command:

fastboot flash recovery recovery.img

You'll have to open a adb/fastboot terminal(cmd in Windows) in the folder that your recovery.img is in on your PC to do the fastboot flash so that it funds the recovery.img.