Lady Stoneheart. I, too, was a bit disappointed that she didn't appear at the end, because, given how she appears in the epilogue of A Storm of Swords, I assumed she would appear at the end of this episode, too. But then when thinking about it some more, and reading some commentary on it elsewhere, I began to realize:
It was because it so assumed it would happen at the end of this episode that it was not included.
Furthermore, as was hinted in that EW interview with Alex Graves, Lady Stoneheart is part of the whole subplot of the Brotherhood Without Banners hunting down and killing member of the House of Frey as revenge for the Red Wedding--and none of the Freys or the BWB appeared at all during this season. That's because, being that this is an adaptation of the second-half of ASOS, they don't appear in those chapters until the epilogue of that book. So while it would've been cool to see the epilogue in this episode, it terms of telling a narrative for this particular season, it would've been out of place.
However, we know that the BWB going after the Freys is much more prominent in A Feast of Crows. Not to mention both Brianne's search for Sansa and Jamie's self-imposed exile from King's Landing also wind up getting mixed in with that subplot in that same book--and it's obvious that season 5 is going to adapt that book along with A Feast of Dragons. That's where we're more likely to see Lady Stoneheart.
And all this speculation that Lady Stoneheart could be cut entirely? I doubt it. After all, we've already been introduced to Thros of Myr and see that he can resurrect the dead. We also know that, in order to properly dispense justice against the Frey's, the BWB need a witness to the Red Wedding, of which Lady Stoneheart is.
So my prediction is that, at the start of next season, Game of Thrones will have a scene from episode 1 or 2 of next season showing Petyr Frey being captured by the Brotherhood Without Banners. Then we'll get another scene where Walder Frey gets winds of this and Merrett Frey volunteers to pay the ransom. Then finally, at the end of that same episode, we will see the epilogue for AFOC. Thus, it sets up one of the narrative arcs for that particular season, culminating in Brianne being captured and Jamie lured into a trap.