This is MCPE 0.5.0 running on Android 4.1.2 (Jelly Bean)
(verified with MCPE 0.4.0 same problem exists, not a regression in 0.5.0)
Also verified Android 4.1.2 with direct WiFi connection between devices, has the same problem. The tablets we have don't have 3G and cannot set up hotspot connection.

Went back to Android 4.0.4 verified with MCPE 0.4.0 and MCPE 0.5.0 same issue does NOT happen. Flashed ICS 4.0.4 on the tablets, MCPE can connect immediately. Flashed back Android 4.1.2 on the devices, devices don't find each other.
In all cases all servers are set to visible.

Other Android 4.1 UDP related comments with no solutions, here: http://stackoverflow.com/questions/12904703/udp-packets-seems-to-be-blocked-by-android-4-1

Let me know if it's possible to trace the failure if it really is a UDP issue.