If a character is stealthing, let's say in total concealment, and its target perceives it by beating its stealth roll, then does the stealthing character have CA against the target?
You gain CA against a foe (via stealth) by being hidden from it.
From the Rules Compendium, page152, Stealth:
If you don't win the opposed check, you're not hidden. If you're not hidden, you don't get combat advantage.