I'll try a slightly different approach to the answer: I'm not sure there are UX problems with condoms. They seem to be a fairly elegant solution to a host of more complex problems. They appear to be fairly self-explanatory once opened. Installation is usually trouble-free.
Now, granted, I've never participated in user testing or focus groups pertaining to the use of a condoms, so obviously I'd need more data to have specific answers.
But to get to that point, I'd try and determine what are actual problems vs. perceived problems. The article that is linked in the question talks about perceived problems. So it's apparent that there are also marketing challenges involved in attempting to increase the use of condoms.
If data shows that there are true physical challenges with the product, then focus would be spent more on improving the UX of the product. If data shows that it's more about perception, then perhaps we'd bring in the marketing department to assist.
I think one aspect of the condom using experience that could be improved is in obtaining the product. Great strides have been made in making them as readily available to those that want them, yet they are still often not the most pleasant product to obtain--especially if you are young. In the US, lots of places put the condoms front-and-center behind locked cabinets. This forces a younger person to deal with potentially awkward interactions with store staff in public. Perhaps one solution is go make sure young people have easier access to condoms (at least in the US, this then becomes less of a UX challenge and more of a political challenge).
In other regions of the world, it appears a major hurdle is education. Wiping away misconceptions about the products. This is likely more of a marketing/PR or Education challenge than UX. I'd first start doing a lot of user research with focus groups and interviews. Based on the data collected, one could then start to formulate education and marketing programs to target the key users.