I had similar problems during the first weeks of MMA beta testing, except it was slow for all UPnP servers; then something changed (in MMA, I think) and it always finds both MMW and the NAS right away. That's with a Galaxy Tab, running ICS at the time.

The time out value for synchronisation could be increased.

I get quite a few time outs during synchronisation.

Nexus 7. WiFi. Big flac files. Nexus shows what looks like a strong connection (all bars).

It all goes through OK if I retry, although I sometimes need multiple retries to get through it all.