It's most likely, because their flags are more than 25 blocks far from each other (this is extremely easy to achieve, even when it's inside the same house, as the example shows) - it works fine with the dye trader, because houses (rooms) are usually less tall than wide, so the dye trader's flag is not very far from the arms dealer's flag.
This is seriously annoying (although this was how it used to be at the start too, when the happiness system got implemented. practically, the only way to have neighbors recognise them as neighbors, to place them extremely close to each other... which is annoying...
edit:
this also brings up that problem again too, that the game arbitrarily decides where to put an NPCs flag inside the room.
on the example, if the arms dealer flad would be placed more to the right, and the nurse's more to the left, they would recognise each other as neighbors, but you can't manually tell there you want the flag, and the game just placed it in bad places.