Bit of background. Your phone has an unlocked bootloader, which means we can load a custom recovery on the phone. This is really useful as it allows you to save a complete backup of your phone including the boot (kernel) and system partitions, as well as data. This custom recovery lives in a separate partition on your phone and means if something goes wrong you can easily restore a backup to get back to a working phone again.
Your phone is also S-OFF, which means that HTC's security flag is switched off. This is an inbuilt safety mechanism as it won't for example let firmware for a different M8 hardware variant model be installed. You have this switched off, but is nothing to worry about just now as we will not be messing with firmware. It is however very useful to have in case something major happens at some point in the future. Your phone can be reverted back to S-ON but I would strongly recommend you leave it as is - it will not affect normal everyday use of the phone in any way, and you don't need to make use of this if you don't want to.
Here's what I suggest we do, and instructions for you to work through. I'd recommend you have a read through it all first, and then work through the steps. It looks like a lot but I've tried to cover each step without missing anything out.
You're going to get a set of tools called adb/fastboot installed on your PC, and then install latest version of the TWRP custom recovery. Then download a stock HTC Sense Android 6.0 (Marshmallow) set of TWRP backup files and restore them in TWRP.
In case you feel more comfortable going fully back to stock, you'll also download the stock HTC recovery and have instructions on how to flash it and instructions on how to relock your bootloader. This will get you back to full stock HTC Sense and able to take OTA updates.
Of course you can opt not to do this, leave TWRP recovery on and start experimenting with flashing custom roms if you want.
This process will not touch the phone's internal storage or the external SD card, but it's always prudent to create back-ups first just in case (we don't know 100% what caused the initial issue or what the shop did so no guarantees).
Some prep first, plus the downloads you need.
If you haven't done so already, backup/copy as much as possible from the phone onto PC.
Get the mini sdktools download from this post:
ADB Guide (updated 2014/11/11)
which also has instructions for set up.
Two things we need to know or sort out first. Ideally we need to confirm your CID number (although I reckon this will be HTC__001 from your bootloader info and carrier), and we also need to know your phone's serial number. You can get your serial number by accessing Settings from the phone app drawer, scroll down and select About or About Phone and it should be in there, or look for another sub-menu it might be in (I don't run CM so don't lnow exactly where). Write it down carefully as you'll need it later (if you can't find it, you'll get it from the following prep step anyway).
Reboot phone to bootloader and plug in to PC (so you see FASTBOOT USB on bootloader screen). Open a command prompt window in the adb/fastboot folder on your PC - if in Explorer hold shift + right click, and pick "Open command window here" from context menu.
Then type:
fastboot devices (to check fastboot connects to phone ok, it should also return the phone serial number - write this down if need be)
If it does, then type:
fastboot getvar all (this is just a check - confirm from the list that's returned what the CID number is eg HTC__001 , you can also double check the serial number as well )
If the CID for some reason is different just make sure it is one of the numbers listed just above the two 6.12.401.4 download links in the first link to the xda post in step 1) below.
As a further check on the firmware you have, make sure that in the info returned from the "fastboot getvar all" command, under Version-main this matches the firmware number 6.12.401.4
Next steps to get you up and running:
1) On PC download the TWRP backup files you need from here:
http://forum.xda-developers.com/showpost.php?p=60211240&postcount=3
pick one of the two download links for 6.12.401.4
Plus the stock recovery, which is handy to have if you want to fully return to stock, from here:
http://forum.xda-developers.com/showpost.php?p=60211779&postcount=4
again, you want the 6.12.401.4 download link
2) Next, do you have a micro sd card in the phone? So you can copy the TWRP backup files you downloaded to the micro sd card and access them in TWRP. The main point to note is that you need to place the extracted files from the zip or rar file in a folder, on micro sd card, with the following name:
TWRP\BACKUPS\
<your phone serial number>\
<backup folder name>
Where:
The phone's serial number is what you noted down - the
<your phone serial number> folder you create needs to match this exactly.
For
<backup folder name> give it a name you'll recognise eg Stock_Backup - this can be can be whatever you like, I tend to avoid using spaces just in case.
The key point is to make sure you have placed the extracted backup files in the above folder, so once we get the later version of TWRP flashed (see below), it will pick up the files for the restore. When you extract the zip/.rar file I suspect you'll find a folder extracted with a name that ends in "... release-keys" it is the files in this folder that you need. You can just use this folder if you like, but as this will appear in TWRP as the backup name I think something called "Stock_Backup" is easier to recognise and deal with.
If you do this before the next steps, it'll save a bit of time.
3) Then download the latest version of TWRP recovery from here, and save to folder on PC where you have the fastboot.exe:
https://dl.twrp.me/m8/
I'd go for at least the 2.8.6.0 version but latest 2.8.7.0 version should be fine. Check the md5sum for your downloaded file matches - the md5sum link is at the top of the website download page, and the mini sdk zip file includes a md5sum checker in it if you haven't got one.
If md5 checks out, reboot phone to bootloader and plug in to PC (so you see FASTBOOT USB on bootloader screen). Open a command prompt window in the adb/fastboot folder on your PC - if in Explorer hold shift + right click, and pick "Open command window here" from context menu.
Then type:
fastboot devices (to check fastboot connects to phone ok, it should return the phone serial number)
If it does, then type:
fastboot flash recovery twrp-2.8.7.0-m8.img (assuming you downloaded the latest TWRP)
4) Then we need to check you can get in to TWRP ok, on phone bootloader screen use vol down to highlight HBOOT from the menu and press power button to select. Wait until HBOOT finishes check (some green text appearing on screen), then select RECOVERY from menu using vol down and pressing power to select.
This should load TWRP.
Then you want to do the restore of the backup you downloaded, so select Restore to get into the restore screen. Now you need to point TWRP to your external SD card, look for the line of text in restore screen that will say something like Internal Storage, press on it and then select External SD Card (or might be Micro sd card, can't recall off the top of my head) - it should be obvious which to select. You should then see the backup listed.
Press on backup name, you should then see a screen with various partitions to restore selected (ticked), there should at least be Boot, System and Data. Then at the bottom swipe the slider left to right to start the restore.
At this point, once restore has completed successfully, I would reboot phone and check it boots ok and complete initial set-up before moving on to the stock recovery step. Check that Google account sign-in, Play Store account and so on are all ok and working successfully. If it boots ok, you might have to reboot back in to TWRP and do a data only wipe if there are any artifacts hanging around from the backup you have just restored. Let me know if that's the case.
[Optional if you don't want to keep TWRP, and get back to stock - I wouldn't until we're sure phone is working ok]
5) On PC, copy the stock recovery image you downloaded to your fastboot folder, reboot phone to bootloader and plug in to PC (so you see FASTBOOT USB on bootloader screen). Open a command prompt window in the adb/fastboot folder on your PC - if in Explorer hold shift + right click, and pick "Open command window here" from context menu.
Then type:
fastboot devices (again just to check fastboot connects to phone ok, it should return phone serial number)
If it does, then type:
fastboot flash recovery recovery_6.12.401.4.img (I haven't downloaded this so the "recovery_6.12.401.4.img" filename might be different, just type this with the correct filename if it is)
This should be you back to 100% stock rom/kernel and recovery i.e. unrooted.
[Optional if you want to go fully back to stock]
6) Then if you want to, the last part is just a case of relocking the bootloader and the phone should be set for OTA updates. At this stage until we are sure everything is ok I wouldn't recommend doing this, in case we need to get TWRP back on. Command for this from PC is:
fastboot oem lock
Let us know how you get on.