Thanks @prathameshp. You pointed me in the right direction and saved me a lot of time-wasting indeed. The link you suggested made mention of some anti-virus plugins conflicting with the subscription service and this was indeed the problem.
I deactivated the WP-SpamShield Anti-Spam plugin and wo-and-behold subscriptions worked for all. 😀
