If I'm right, the key to this situation isn't about making your characters too awesome or not real enough. It's about making sure they struggle despite their awesomeness.
I think there's a lot of truth in that. But I would add one thing: The longer you're with the character, the more variety of struggles you're going to need. That's one of the issues I have with Superman. He's great for a movie or two, but eventually it's: What shape is the kryptonite going to come in today?
I think the conflicts have to be in some way appropriate for the character. I want to learn more about the character from the way he tackles conflict. The more Mary-Sue-awesome the character is, the bigger the conflicts have to escalate, and that creates new challenges in finding conflicts that are appropriate.