First, I think a little more context may be needed to appropriately answer your question since it seems whoever you've been talking to has what I would consider to be a non-standard usage of it. That being said, here's my best cut.
In standard usage, the phrase "not uncommon" typically means something to the effect of "more frequent than uncommon". That is, it occurs too frequently to be considered "uncommon", but not necessarily so frequently as to be labeled "common".
However, in certain contexts where things are partitioned using discrete, well defined terms "uncommon", "rare", etc. it would be conceivable that they would mean "anything other than uncommon". The one example that jumps out at me is RPG games like World of Warcraft where item quality is labeled using terms like "rare", "uncommon", "common", etc. In a case like this, saying that something is "not uncommon" would potentially allow for something labeled as "rare" as well as something labeled as "common"