I had the same problem as most of you are describing here and I got it working.
Tl;dr: Call your ISP and have them update the firmware in their router. My ISP (Fullrate, DK) had a patch ready specifically for the AirPort Express.
The gist of the setup: AirPort Express 2012 with latest firmware (bought less than two weeks ago). Set up to join the network existing network (aka client mode). Connected to an amp through the jack port.
Problem #1 (diff. problem): For starters I set it up with an iPhone through Wi-Fi settings and it seemed to go smoothly. I went into the Music app and it worked. But in iTunes on Mac it would time out, unable to connect. But at the time I solved it by turning off IPv6 on the Mac as suggested elsewhere.
Problem #2 (what's discussed here): Then I experienced what most people in here describe. Both on a Mac and an iPhone. It would work well to begin with, but then if you paused it just for a little while it would err (Error code -50). Interestingly it would be marked with a warning sign in AirPort Utility (as in, it had become invisible) but still stream successfully. But then if you paused it wouldn't be able to pick it back up.
Problem #3 (also diff. problem): Just for fun* I configured the Express to create its own network instead. That meant having to connect it to my ISP's router. But the Express refused anything was connected. I don't know if this has also been solved as I haven't tried that configuration again, but it might have been. But I could connect to its network and stream music, I just couldn't go online.
The solution: The folks at Apple Support suggested two things: Creating a new network (unsuccessful) and call the ISP because they might know which ports to unblock to get it working. I called the ISP and they applied a patch to their router specifically for the Express. I don't know if unblocking ports is what the patch did, but it solved the problem.
Hope this can help some folks in here. :-)