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.