Fine Stitch on Avenue B. A chinese lady who speaks pretty decent english. I had a pair of pants hemmed and a few darts put into my shirts. The work was carefully done, and the hem was hand-stitched. It was also really quick. A couple of days for anything. Be warned though, the location is a bit odd.
I don't know about more complicated stuff, but the lady who had come in before me raved about an apparently innovative placement of elastane in her dress.