I think most Android users who've downloaded an app recognize the Market. It should be ubiquitous on Google approved Android devices - I'm sure a gift card with an Android on it and the Market (well, Play) logo should be fairly recognizable.
And even then, Google just opened this Play thing, no Android logo in sight. What the hell is going on there.
I think if you are a nerd and stuck in the middle of it you can’t really see the craziness of it all, but believe me, it’s crazy.