When you playback in VLC, look at Tools > Codec info? Is there one set of audio and video, or two? If there are two, that indicates that UDP ports are blocked or not mapped properly. VLC is able to failover from UDP to TCP, and that is why you see two audio and two video blocks in that case. However many Android and other devices use UDP and are not able to failover.
Otherwise, it might be an encoding problem. Make sure it is h.264 Baseline 3 or lower video, and AAC audio is recommended.