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:
Opposed Check: Against the passive Perception of each target creature present. ...
Success: The creature becomes hidden from the target.
If you don't win the opposed check, you're not hidden. If you're not hidden, you don't get combat advantage.