Firstly, this isn't a specifically British construction, nor is it the standard in British English. It's just a nonstandard variant that occasionally occurs in both American and British English. (More on that later below.)
As for an explanation of why it is used, I guess some people either understand the word "miss" differently than we do, or just aren't thinking clearly.
A different understanding of "miss":
"I miss not having him around" seems like a cross between "I miss him" and "I regret not having him around". The standard meaning of "I miss X" (in our context) is something like "I feel a sense of absence or loss because X used to be around and isn't any longer", thus "I miss having him around". Some people appear to be extending/inverting it to "I feel a sense or absence or loss because of X" (see the quote *"I miss that he is not around any more" in the other answer) thus for these speakers, "I miss not having him around" means "I feel a sense of something missing because of not having him around."
You can see this most clearly in the American examples:
"Do you miss not having children?"
"I feel that as an only child she may miss not having siblings later on, as an adult."
where there is talk of missing things that one never had, and
Q: Do you miss not having hands and feet?
A: Well, I've never had them.
Here the question uses "miss" in the nonstandard sense ("do you feel something missing because of not having hands and feet", a rather daft question), while the answer, having ignored the not (and the literal meaning), treats "miss" in the standard sense: I can't miss something I've never had.
As for why this different sense comes about, I guess there's a strong temptation, in phrases involving counterfactuals, to state the factual instead. (I suspect something similar was at work in the origin of "could care less", sometimes claimed to be sarcastic though it's not.)
Not thinking clearly:
This actually happens naturally in language. It's not unique to this phrase; there's a small amount of confused inversion in many phrases involving negatives:
- People frequently say "You can't fail to miss it" when they mean "you can't fail to see it" or "you can't miss it".
- They say "No one can deny that X is not the best" when they mean "No one can deny that X is the best" or "No one can claim that X is not the best"
- They say "No head injury is too trivial to ignore" when they mean "No head injury is so trivial that it can be ignored", or "No head injury is too trivial to take seriously".
- Even laywers get it wrong, and
- The non-logical usages are often far more common
I guess that, with time, "miss not" will join the list of phrases like "could care less", "doesn't know squat", and "teach you to", where a negation can be added or removed with no change in meaning. So this inverted usage of "miss" may well become standard, and it will only be considered to add to the glorious irrationalities of the English language. (In the Corpus of Historical American English, usages of "miss not" before 1968 are mostly the "correct" one, while 1968 and later has mostly the usage you asked about in the question.)
Corpora indicate it may even occur more often in American English than British English, though more below.
The British National Corpus has only five instances of this usage, all from fiction:
"we miss not having your funny face around to laugh at",
"I miss not having one",
"D'you miss not drinking very much?",
"Did you miss not 'aving me to talk to?",
and one that, interestingly enough, uses both the "miss not" and "miss" constructions in a single sentence:
"I often think I miss not having someone with whom to share the joys of Dickie, far more than I miss having someone with whom to share my worries."
The Corpus of Contemporary American English, however, has 20 instances of such usage (leaving out phrases like "miss not only…"), from news, spoken TV programmes, magazines, fiction, etc., e.g.:
"BH: Do you miss not having children? Calhoun: Yes. You know I love kids",
"Do you ever miss not having a daddy?",
"I will miss not being able to walk Christie down the aisle",
"I miss not having the late Red Auerbach to answer such vital questions",
"I miss not being able to talk to people in the market",
"I miss not being in a more cosmopolitan city",
"'Do you miss not having hands and feet?' Well, I've never had them.",
"I miss not being able to see my friends' faces",
"I miss not having my dog around",
"I feel that as an only child she may miss not having siblings later on, as an adult.",
"I kind of miss not being able to drop by my parents' house during the week",
"Cmdr. VERNOSKI: Listen, do you miss not having my long hair on the rug? Col. VERNOSKI: Absolutely! I miss not having your long hair in my hands."
It does contain one "correct" usage of "miss not" as you and I seem to understand it:
about having the disease? […] I miss not having to think about this. I miss just going to work and leading…
Of course, probably the two corpora aren't the same size, but I don't (from looking at them) see any clear justification for calling it a British construction. And from the relatively small number of instances, it seems less frequent than the "miss having…" variant.
Another way of looking at them is through Google n-gram viewer. I don't think this is extremely reliable, but worth looking.
Here are "miss having" and "miss not having" in American English:
And in British English:
Similarly, here are "miss being" and "miss not being" in American English:
And in British English:
So from the data it seems (look at the numbers on the y-axis carefully) that "miss not being" and "miss not having" are used at about the same frequency in both American and British English. But "miss having/being" are used much more in American English, so the "miss not" forms are more common in British English relative to the standard forms. Still, less frequent. (This is a crude search without context, so all the caveats apply.)
Edit [2011-11-23]: The Language Log has had around 75 posts on this very topic. It has been enlightening reading several of them, but I am too exhausted to summarise them here, and I recommend you to read those posts directly.