The trick to easy stitches isn't the brushes. I'd say about 90% of stitches are pretty simple ones, so really you just need a round brush that's been made into a really thin oval, sized, and spaced to work. Even a zigzag stitch is pretty easy to make yourself. The trick is that you should have them follow a path rather than painting them by hand. It's like the difference between using a pattern and sewing by eye.
In Photoshop, this means making paths and stroking them with a brush designed to follow the path direction. And if you map your clothes well, all you need to do is outline your islands, inset your selection by x number of pixels, and create a path from that. Takes only a few clicks in Photoshop, which is why I tend to keep at least one mask layer for islands and layers with patches or embroidered bits on their own layers. I have no clue how to do any of this in GIMP, but that's my suggestion on workflow.
Oh! And give your stitches layer styles for different types of maps (diffuse/albedo, bump, displacement, etc.). You can overlay them with a texture, give them a bit of drop shadow and black "glow" for depth and all kinds of stuff. And save your styles so you can apply a default base and just tweak things like shadow size and opacity.
IMHO, the hard part isn't making one good texture. It's making several sets of good textures. I don't think I've ever been able to get faster than one whole set per day, but I tend to like layered materials with about 4 to 6 different maps per set. Well, I do for clothes, at least. It's a really good thing I'm going to be focusing on architecture.
