I don't have a specific address in Palermo, but what you're looking for is a mercería. Most neighborhoodshave them tucked away, like cotillóns, but you have to find out where they are. Maybe start asking around? I remember buying some needles and thread a long time ago up Scalabrini Ortiz on the other side of Cordoba towards Corrientes (in the yarn area), so I'm sure there are several mercerías up that way.
Otherwise, there are many stores on Lavalle between Puyerredon and Azcuenaga, more or less. This is the fabric/costuming district, and there are stores that have wide selections of colors of embroidery floss, needles thread, etc.