Not at all pure LEGO, but after a while I gave up trying to emulate a real sewing machine mechanism, and just went "embellishing" a real machine. Therefore, this is more of an "NXT-assisted" embroidery, than a pure solution. It's still a rather rough prototype, but it has proven the concept as worth the R&D.
The X-Y fabric movements are simple - I've had much more trouble motorizing the handwheel (absolutely no grip, and occasionally huge torque required). Needle movements are imported from a program EmbroiderModder.
Finally, some embroidered Classic Space, Technic and NXT logos for my bags and blank baseball caps :). A bit of extra text is here, and a YouTube video
.
Result that came out of the prototype after about 30 minutes of work... (the rusty old look is intentional - it can be avoided by using top and bottom threads of identical colours, rather than white & brown).