The version of that story that I hear most often is that Katie Holmes was a studio choice for the "love interest" for Begins. That is wasn't entirely upto the filmmakers. Then just as promotions ramped up for the release of Begins, the whole "TomKat" ( :angry-banghead: ) phenomenon happened and all hell broke loose. I think from what everyone at the studio and the creative team viewed as bad publicity, or her not helping to publicize Begins but instead her relationship, and also that the filmmakers felt Katie Holmes was a bit out of her league with the rest of the pretty stellar cast, they decided to cut her loose. From her side, she couldn't do TDK because she had committed to Mad Money and the timing was bad. I think there's some truth to both sides but more so from the studio side because who in the hell wouldn't want the publicity of that sequel at that time?? Only to instead opt for a below average at best, chick flick. TDK was HIGHLY anticipated. I really can't explain the choice for Maggie Gyllenhaal. Maybe it was a 3 degrees of separation thing since Ledger had recently worked with her brother Jake on Brokeback Mountain. I don't really disagree, that maybe they could've found someone a little more drop-dead gorgeous with the acting chops as well. But that's really not what Nolan seems to be about. I guess for continuity's sake I'd prefer that they just suck it up and bring back Katie Holmes but I don't have as big a problem with it as others do. But I see where the detractors are coming from.
* On a side note, a lot of people have no idea that Maggie Gyllenhaal had just had a baby prior to shooting the movie. So that may have contributed a little more to her "frumpiness", of course if you also don't care for her acting then it doesn't matter either way.