In the case where profanity is being used in a manner a reasonable person could take offense to (particularly direct insults) then other rules of social conduct (those commonly observed in life and any specifically stated in your rules) are in play. You are not trying to stop them using expletives you are stopping them cause offense - they could cause the same offense without the expletives (though swearing is the easy/efficient way). In these cases profanity is the transport not the message and it is the message that you have a problem problem with.
In the more general case perhaps rather than simply saying not to overuse profanity you could explain why it is a bad thing. The obvious one is "it just looks childish and brings down the apparent tone of the group as seen by both members and outsiders who might consider joining" but you need to be careful how you word that because a sensity person will read "this particular behaviour looks childish" as "you are completely immature" and take offense themselves (which seems to be happening already given that they are feeling "punished" when you question their use of language).
Another tack you could try is to point out how overusing expletives and other profanity diminishes its power. Profanity when used sparingly is a very powerful way of expressing extreme emotion and serious reactions but when used all the time it just becomes the norm so when used to express an extreme this simply isn't noticed. For example: if you don't normally call someone a "c" but do in reaction to something they've said they and any spectators know they've gone to far in your view (and pushed you to go somewhere linguistically that you are normally not to tread), but if you call them a "c" all the time that difference no longer exists for anyone to notice. At that point we are no longer able to make use of the expressive power profanity offers and it simply becomes filler: wasted words. As the point of a discussion forum is generally to put across thoughts/reactions/ideas efficiently and concisely (because such concisesness often aids understanding in the reader) poinless filler, in this case overly regular profanity, should be frowned upon. That came out a lot more long winded than I intended, breaking my own conciseness rule, but perhaps you can base a more efficient explanation/rule based on it!
When warned, the users say that we have no right to punish them as profanity is allowed
You have every right, such right is granted to you be being awarded (by yourself or others) moderator status, so you can legitimately tell them they are wrong there. If they don't like the rules of your forum the democratising power of current technology allows them to create their own where they can interact with like minded people while not bothering you.
Their "freedom of speech" does not invalidate your freedom to chose not to put up with them!
or just simply ignore us.
- Warn politely
- Warn more sternly
- Final warning
You might make the process more detailed by adding in temporary bans or forcing people read-only rather than a complete ban, and so forth - what works best varies from community to community. Again point out clearly that if they don't like the rules of your forum they are perfectly free to start their own and invite people into it.