Damian Lewis is pretty much perfect for the new Matt Murdock. Check him out in Dreamcatcher, Band of Brothers, or Life. The guy is just a phenomenal actor, and he really looks the part.
Elektra needs to be more.. exotic. Refined. Sexy. Strong. Garner was great, but just not right for the role. British-born, raven-haired Rhona Mitra (The Number 23, Nip/Tuck, Shooter) would do an amazing job with the role.
Bullseye needs to be silent, strong, brutal. He can kill without a thought. He can crack wise a little when he feels like it, but he's, for the most part, a silent, trained killer. I can't think of anyone but Jason Statham. He's just darn perfect for the part.
Whoever first suggested Chi McBride as Kingpin, good call. He's the only actor around who could really give the role some justice. He can be tough, cool, smart, and, overall, a badass. He can also bring a little more class and dignity to the part than Duncan could.
As for Foggy Nelson, Matt's chubby and jovial law partner, the perfect man is Andy Richter. He's funny, charismatic, and can really act when he has to. Plus, he just looks the part so well.
Karen Page needs to be the light of Matt's life whose death absolutely sends him into a terrible spiral. She needs to be sweet and beautiful to make her downfall and death all the more terrible. Parker Posey is a great actress who has a natural sweetness to her. She'd do the role justice.
As for the story, I don't really know. We can't bring in Elektra and Karen and kill em both off. It'd be.. repetitive. Too dark. That would have to be split over more than one movie. I'm honestly not sure how I'd tell that story..