Pode ser que o provedor de hospedagem esteja com defeito. Você pode tentar traceroute -n -U -p portnumber hostname
de uma máquina cliente para ver até onde os pacotes UDP chegam. Ao fazer isso, você pode usar tcpdump -pni eth0 "port portnumber"
no cliente e no servidor para verificar se pode ser o caso, que os pacotes deixam o cliente e nunca chegam ao servidor.
Se o acima mostrar que os pacotes deixam o cliente sem atingir o servidor, então qualquer NAT ou firewall no caminho do cliente para o servidor é um suspeito. A saída do traceroute deve diminuir os suspeitos.