After running stop-dfs.sh followed by start-dfs.sh from the Namenode, one of the Datanodes raised the error:
Cannot write datanode pid /tmp/hadoop-hdfs-datanode.pid
I checked the permissions for the hadoop-hdfs-datanode.pid and the hadoop user had permission.
Note: I've already solved the problem, I'm posting this for future as I was unable to find a solution online.
It turned out the machine running the Datanode was out of space and this wasn't reflected in the raised error. df -h is handy for Debian systems. After cleaning some space and running start-dfs.sh from the Namenode all Datanodes were running successfully.