Parece que o problema era a taxa de análise (muitos pacotes por segundo?). O uso do parâmetro --max-rate
tornou o desempenho muito melhor. Leva muito tempo para ser executado, mas pelo menos funciona.
$ nmap -sP --max-rate 1 192.168.2.0/24
...
Nmap done: 242 IP addresses (67 hosts up) scanned in 434.04 seconds