The calories-in calories-out model is attractive, but it doesn't appear to be all that accurate, or at least it's incomplete. The body responds differently to different foods. They might have different effects on various hormones (e.g. the ones that regulate hunger), and they might be broken down and redistributed in different ways. In one study (Kekwick and Pawan), three groups of people were put on 1,000 calorie diets of 90% fat resp. 90% protein resp. 90% carbs. The first group lost 0.9 lbs / day, the second group lost 0.6 lbs / day, and the third group gained 0.24 lbs / day. (I don't know to what extent the study controlled for exercise but I think it's safe to assume that the difference in the amount of exercise that each group did wasn't large enough to explain these results.) As Tim Ferriss puts it in The 4-Hour Body:

The creator of the "calorie" as we know it, 19th-century chemist Wilbur Olin Atwater, did not have the technology that we have today. He incinerated foods. Incineration does not equal human digestion; eating a fireplace log will not store the same number of calories as burning one will produce. Tummies have trouble with bark, as they do with many things.

In the context of solving the specific problem of fat loss, one goal is not to lose muscle, and what you're eating should affect how easy it is to target fat and retain muscle as well.

And, of course, diets don't work if they can't be maintained. The fact that different foods affect the hormones that regulate hunger differently (some foods even make you hungrier!) means that different diets, even with the same number of calories, require different amounts of willpower to maintain.