I discover this question nearly ten years later, but seeing both it and its responses relate to things that somebody once paid me to spend a considerable amount of time upon, i feel i have to add some bits, if not for the original poster anymore then for others who might follow up in this vein.
The goal from the outset was pretty much what the original poster had in mind: find a set of phonemes that is fairly easy to produce and reproduces for as many people as possible. The approach that i followed was, just as suggested, to trawl through UPSID, take notes of everything, and discover a list of phonemes that fits the description so that it could be used in an AuxLang.
While I'm not going to disclose my results (even though the project ultimately deviated from them), i'll point out that i have come across several studies of shared features of phoneme inventories of Creole languages (use Th Klein, 2006, "Creole phonology typology" for a starter) point very much in the same direction.
But, some insights based on things i still remember:
- One might think "phoneme" is clearly defined, but they're anything but simple. For example, should one count diphthongs as one vowel or two? If they are single vowels, then how should one deal with those occasional triphthongs? And while were at it, should one follow the book by assuming affricates as single consonantic phonemes, or would it better to treat them as two separate and separable consonants? And what about approximants (think of English ⟨Y⟩ and ⟨W⟩), vowels in every sense but their consonantic actual use?
- The things that proved most annoying as i followed this path were suprasegmentals. Initially, the idea was to simply ignore stress phenomena and tone, and that should be it. But... while busy deliberately ignoring how unexpectedly many tonal languages there are, i'd realize that length is similar, so should one treat long vowels and/or long consonants as one or two of their kind each? And yes, this proved to connect to the diphthong/affricate question from above. And then there's short vowels, too, rather indicated than pronounced (if you don't know what i'm thinking of, look at Japanese). Also, what's happening with instances where only the onset of tongue movement makes a difference (as in "ew" vs "you")?
The one thing that work in this project really brought home to me was a clearer understanding of what my phonology teachers had had in mind when they pointed out the relational nature of phonemes: the phoneme itself is not all that important: the thing that you really want to figure out for your AuxLang are the most common distinctions between phonemes.
For example, some languages distinguish (syllable-initial) among bilabial plosives between voiced and unvoiced, some between unaspirated and aspirated, some cross these two for a fourway, some palatalize or velarize or whathaveyou... and some have only |b|, or only |p|. So if we're serious about wanting to make it easy for people to learn the language, we shouldn't force them to pronounce exactly [+voiced -aspirated -palatalized -velarized -breathy] or [-voiced -aspirated -palatalized -velarized -breathy] and not any of their native variants... we should try to map these distinctions one on another so that speakers realize that their voiced/unvoiced is my unaspirated/aspirated or nonpalatalized/palatalized, and trust on them to realize that their interlocutors' pronunciation may be slightly accented because of their native language, but still reasonably comprehensible. And if there is a distinction that is not common, don't try to push it on people. (I've heard enough Italians trying to cope with German vowels, i know what i'm talking about.)
So: anybody: if you are in it for this particular goal, and up for the long trawl through UPSID, don't simply repeat in the tracks that appear untrodden. Trust me, i did walk there, decades ago. No doubt you'll learn a lot, but i've already highlighted (what i consider makes out) a fair deal for you, above. Rather, try go to a new level when you're there: look into the distinctions between phonemes that are employed, and try to map the most frequent one on each other in a way that'll let people in, rather than keep them frustrated on the outside. (Do take me serious: just adding vowel length to the Creole-like inventory i mentioned above will considerably reduce ease of acquisition for about 2 out of 3 learners. You wouldn't want that.)