My take (after much consideration):
Stealth is something that you perform an action doing, not a condition
So: If you want to attack from stealth, check to see if you meet the conditions, make the check, then attack. If you want to move while "stealthed", check to see if you meet the conditions, make the check, then attack.
The concealment from Shadow Walk happens after the move that puts you at least three squares from your starting position. Using that concealment, you can then make an attack using Stealth, or you can move again if you don't want people to know where you are.
Why the attack itself is "stealthed": You have concealment, so your opponent cannot clearly see what you're doing. It's like keeping a gun hidden under your coat. Also think of the "Stealth using distraction" as the old "look over there", or when you psyche someone out by pretending you're going to throw the ball at the someone else. It's only granting combat advantage, which basically means that they're not reacting correctly because they can't fully judge your intent. The attack itself blows any Stealth you have.
You still keep all the advantages of having concealment, and can even use "Stealth" as normal on the next round (Or even: Stealth Attack, then Stealth Move at least 3 squares to keep it going).
Everything I've said should be well within RAW, and seems to be RAI, and doesn't "nerf" any ability (and doesn't get anything out of hand, either).