I encountered the same issue. After searching and reading different things online, what worked for me was:
$ brew postinstall node
However, first please do execute:
$ brew doctor
and follow the instructions there first, like the comment in your question mentions.