I managed to fix it!
I did a general search on Google about not being able to save images and came across the below thread:
A member there suggested to use Google Chrome and load the half-page editor (by pressing Ctrl+Shift+J) and see if any errors appear when trying to save the image. This is what I got:
POST http://www.mysite.com/wp-admin/admin-ajax.php 500 (Internal
I then looked up that error on Google and found a few users talk about updating the server mod security/cpanel settings. So I emailed my host and this is what they said:
"Most likely this is a mod_security issue, yes. graqpping for the IP you opened this ticket from in the Apache error log reveals:
I've whitelisted against this URI and rule-id. Please attempt again and let me know if the issue is resolved or persists."
This fixed the issue, I can now finally set featured images again!
Hope that helps.