Similar happened to us. We are new to keeping chickens, but all has gone well. We got 3 small "pullets" form a reputable breeder, but they were still very young and he did say that it's difficult to tell that early. I kept expecting the slightly older and bigger one to start laying in about 15-16 weeks from the purchase, but never did. We posted pictures here and members informed me that it was a rooster! So we took him back and traded him in for another hen for sure. The established ones picked on her at first and I had to keep them separated for a couple of weeks, but the new one is much larger and a different breed, so she can take care of herself now. She just started laying big brown eggs - in the middle of winter! It's easier to tell with some breeds more than others. If it's like the one Flockmaster posted, it's easier, but mine were all white so the feathers weren't as obvious. If you need hens FOR SURE, go with a sex link breed so no question.
