Any chance you have a DMZ set up on your router?
On your router, are there any settings specific to any host (other than the server maybe)? For example, a static IP or a port forwarded rule.
Do you have a VPN on the phones? Can you traceroute from your phone to the server and post that? (I like PingTools for Android.) You should have 1 hop (you -> server, nothing in between).
Can you verify that you are on the same wifi including same wifi channel? Phone on 5GHz but Linux box on 2.4GHz, for example.
Linux is just as bad though
.zsh_history
records every command you run!(/s, obviously...)