Documenting some new (hard won) findings in case anyone else comes across this and struggles like I did.
This error was initially caused by this (incorrect) setting in the elasticsearch.yml file:
Changing it to true allowed the node to generate a token.
But more importantly, an Elasticsearch instance installed on Ubuntu/Debian with apt will already have security setting in the config file EVEN IF it has never been started. So in my mind at least its a bit half baked, as in, some documentation suggests that with a new node, you must start Elasticsearch for the very first time with a token generated on another node. But this fails if ES was installed with apt and has some ready-and-waiting security config. I wish the error message would be more clear about this. In this case, you need to run elasticsearch-reconfigure-node first.