In this instance, you could say there are two distinct routes to social activity:
1. Meeting like-minded people through a common interest in a shared activity
For example, if you were interested in comics and attended events like comic conventions then you are going to be exposed to people with a common interest. The people you meet aren't going to be identical to you in every way of course - we are all unique - but you have a shared interest which could be the basis for a friendship.
2. Meeting differently-minded people by coincidentally sharing a space.
Some people make all their friends at school, or at work, which when you think about it does not guarantee you have any shared interests. But this isn't a bad thing, because it isn't necessarily good for us to only associate with those who may think the same way as us. To be rounded as people we need to broaden our minds to other ways of thinking.
Smoking is what has brought you together with a number of people that you clearly enjoy associating with. Maybe you do share some things in common - but it wasn't those things that brought you together. Smoking can't really be called a shared interest - lets call it what it is: an addiction. Anyone can become addicted to cigarettes. Also, if your daily contact is limited to talking in the place where you take your smoke breaks you are never really sharing in any other aspects of your smoking buddies' lives, so as real as these friendships are they are pretty limited.
You don't have to ditch the friends you have made. If you think there is scope for continuing friendships through other activities then extend offers to them. Try to avoid situations where smoking could take place so that you aren't tempted to return to the habit.
But as for making new friends - look at the two routes I mentioned above. If you have interests already then see if you can pursue them any further in ways that may introduce you to other people. If you don't have an interest like that then have a think about taking something up - there are probably running clubs, choirs, craft clubs - all sorts of activities operating locally, you just need to look around.
But if you prefer the idea of meeting a wider range of people rather than base friendships on an interest then look for other social opportunities at work. Rather than the smoke shelter, is there a common area for coffee breaks? Talk to people there. See if there are social clubs at work. If not, you could take the initiative to organise something like a work night-out.
Also remember that you meet people through people. Accepting social invitations from people that you might not have much of an affinity with can lead to you meeting others with whom you get along better.
I should add that I am not a smoker or an ex-smoker. But this isn't a situation that is exclusive to ex-smokers. People relocate and have to find new friends. Sometimes a bad break-up can divide social circles. Lots of people successfully make new friends and I hope that you stick to your resolve of living healthier.