Lindsay -- one of the important functions of the genitive case in Russian (whether singular or plural) is to indicate the ABSENCE or NON-EXISTENCE of something.

Thus, туфель is genitive plural, indicating that the man ain't got no shoes, while туфли is nominative plural, because there are shoes on the woman.

Other examples of the genitive being used to show that something is absent, or doesn't exist at all:

У меня нет собаки. = By me there is not a dog. = I don't have a dog. -- собаки = gen. sg. of собака (fem.)
У нашего друга не было сахара. = By our friend there was no sugar. = Our friend was all out of sugar. -- сахара = gen. sg. of сахар_ (mas.)

If the man had his left shoe, but was missing his right shoe, then you could say (following the pattern of the examples you gave):

На мужчине левая туфля, но правой туфли нет.

Here, the adjective "left" and the noun "shoe" go in the nominative singular (because they're THERE), but the "right shoe" is in the genitive singular (both the adj. and the noun), because it -- isn't.