It may or not be what CannedMushrooms has said for you guys but I had a problem eerily similar to that of the OP and it was fixed by exactly the method CannedMushrooms says (after much weeping and gnashing of teeth).
In maya before the export, go to UV map editor, grab the map and scale it down so nothing touches the edges.
There’s more: try to make sure there are no overlapping UVs because Zbrush doesn’t like that.
Also: a little trick inside of Zbrush: You have to make sure to have SUV on when subdiving organic shapes. Once you subdivide up high, go to create texture and then do “create texture from UV map” to see if anything happens bad. At that point you will see if the UVs have screwed up or not.
For non-organic shapes make sure both SUV and Smth are OFF before you try subdividing. Do the same test to make sure that the UVs haven’t freaked out during subdividing…
Hopefully this will help someone.