It's pretty tough to sex a very young Bristlenose catfish
They were right in the shop, the ability to determine the gender of these catfish gets easier with age. During their earlier months, both males and females look almost identical. Whilst the female could be very slightly bigger than the male, it's pretty dependant on the individual fish so not that much certainty can be had.
When are they old enough to sex?
Again, this kind of depends on the specific fish, diet, environment and a number of other factors but when they're around 4 - 6 months old you should start to see some subtle differences between the two sexes.
What are the differences I'm looking for?
Males will grow spikes on the top of their head and around the front of the head. Here's my male bristlenose (~ 1.5 years old):
The spikes on this one are still growing but when you compare it to the female below, you'll see how the female (~ 2.5 years old) looks completely smooth around the mouth:
You'll hear people talk about females having spikes too. They do but they are much smaller around the sides of their face:
They use these to show dominance and make displays and both the males and females have these. The difference is that the male has spikes all over their heads too.
Finally, females are said to have rounder, fatter bodies but I've personally found this an inconsistent measure and is very subjective depending on the size of fish itself.