Are they?
Phoneme definitions are language-specific. The French “euh” phoneme doesn’t even exist in English, and I don’t think the American “uh” exists in French either. In that situation, what does it mean to say they’re “different phonemes”? Surely it’s not the usual criterion that their difference can be used to tell two otherwise identical words apart.
And across languages, it’s certainly possible for a sound that’s a phoneme in language A and one that’s a phoneme in language B to be practically identical. It’s a truism that every language has the vowel /ə/, for example, because it’s just the sound you get when you articulate as little as possible. (And laziness is universal.)
And if the Americans are used to having their tongue roots a bit retracted, and the French are used to having their lips a bit rounded, then what we’ve been describing as “uh” and “euh” could be thought of as their local varieties of /ə/, no?