After entering the relevant details such as Subscription ID, Certificate pfx file and password, I was greeted by a not too helpful error message of "Service Unavailable" with no further details.
After scratching my head and trying several things such as deleting the certificate and re-adding it to Azure, checking firewalls etc I remembered this server had just had a restart.
I checked the services to make sure everything had started up ok and noticed that the App Controller Windows Azure Provider service wasn't started.
I started the service, tried adding the subscription again and voilà! It works.
I hope this helps someone else if they get this generic undetailed message.