So, as an initial disclaimer, I remember next to nothing about Disney's Sleeping Beauty so whatever I'm writing here has little to no reflection upon this film as being a reinterpretation of that as source material. What I am covering is it as a new fairytale (in a literal sense in this case, since this is a tale about the Fey & Humans as seen from the perspective of the Fey, rather than the Humans) within the trappings of Sleeping Beauty, and why it works.
Now, the film isn't perfect. It gets a little jumpy at times in terms of the pacing being inconsistent, and some of the final fights are a bit choppy (sort of the way that the fights are in the LotR films after you've seen the extended editions and then go back to watch the shortened versions - a bad analogy but the first thing that came to mind). However, absolutely NONE of that even comes close to overshadowing all of the things that I loved about the film.
The Basic Narrative: At its core, the story is really about the Fey vs. the Humans. They live separately and are completely and fundamentally different. The story is about many things, but is ultimately always some form of that story. It's also a story about revenge and hatred (or in the terms that my roommate so eloquently put it, "Proof that Jesus really CAN microwave a burrito so hot that even he can't eat it."), and the issues that that causes. Additionally there is a message about relationships and true love that I really enjoyed as well.
The Fey: Oh my. Where to even begin. They have everything. There are little water faeries who dance across the water's surface with perfect elegance and grace, there are odd, shy little mushroom-covered fey, there are the three main short-attention and self-focused little fairies, there are the large and almost weightlessly majestic draconic fairies, the cute little glowing firefly-like sprites, the completely insectoid little fairyfolk, the mischievously playful elephan-frog fey, the imposing and old tree-guardians like Balthazar, and the exceptionally majestic and powerful Maleficent. They manage to have the full range of Fey that encompass everything about how very much NOT human they are, and that's important. You immediately understand why the humans aren't allowed in the Moors, and not just because the iron burns the faeries' skin - it's the most simple point that the basic worldview of the two is completely different as shown when Maleficent drops the gemstone into the lake, and Stefan sees it as, "Throwing it away." whereas Maleficent sees it as, "Returning it back to where it belongs."
Maleficent: First of all, Angeline Jolie is an absolute goddess and is the central pillar upon which the ENTIRE film is held up. She brings all the mystery and fear that she has as Grendel's Mother in Beowulf but with far more, since the story here is being told from the Fey's point of view. She's the powerful protector of the Moors, and all of the fey stand behind her, since - as fey are want to do - they often squabble amongst themselves and don't see eye to eye, but they always respect her. You can see her young curiosity towards the outside world the way that she falls for Stefan because he does a little thing like casting away his iron ring so as not to hurt her, and that memory grows with her, so that she always remembers it, and doesn't notice that he doesn't see her the way that she sees him. After he takes her wings from her, even the act of needing to walk is a painful reminder of what was taken from her. We also see that when she is using her magic that is coming from the seething hatred that she has for Stefan, it is the malevolent green that we associate with Maleficent from the human version of Sleeping Beauty, but here we get to see that her natural magic is a golden hue. It's this change that brings the shadow over the Moors and turns her into a much darker protector - raising up her thorn walls.
Her relationship that she forges with Diaval is exceptionally grand. She's curt with him, because he reminds her of all the things that she can't do on her own - especially flying, so she is often dismissive of him, but they have a really honest friendship in that they bicker amongst each other over little things like being turned into a dog, or her telling him not to come into the castle, which makes him feel less important, or even snapping at him dismissively when she saves Aurora from tumbling off a cliff, which makes the idea of their friendship afterwards even better. This is especially important, because the three fairies who "raise" Aurora don't listen to anyone - especially not each other, so it's of NO surprise that they arrive at the christening, despite knowing that Maleficent wouldn't approve. They are just incompetent at raising a child as you'd expect from the fey like them, and SO much worse as soon as they're forced to be 'humans.' It's even better, because they're the sort of caretakers who really wouldn't notice if Aurora wandered off for huge lengths of time, and would be entirely oblivious to Maleficent's frequent presence. What this does is open up an unexpected door:
Aurora: Aurora is everything that the fairies blessed her with. While she is initially the source of Maleficent's revenge, and quite the, "curious little beastie" to the queen of the fey, she's utterly endearing. Since Maleficent initially starts by micromanaging for the utter incompetence of the three fairies, it slowly builds up something important. Aurora loves the Fey and their world. It isn't the sort of perceived love that came from the treacherous relationship that Maleficent experienced. As Aurora spends time with the Fey, you get to see the qualities return to them, as well as those things comes back to Maleficent herself. There's the elegance and beauty of the water faeries that she sits and admires, the way she pets the snout of the draconic fey with gentle care, and even plays in the mud with the little elephant-frogs. Each time she seems fey and interacts with them, a little bit of the shadow that fell over the fey of the Moors and made them subservient to her will when they all bowed to her, slowly peels away to the light that Aurora brings. That's why the love that Maleficent has for her grows into something true, because Aurora is literally all the little things that she missed and that vanished from her life after Stefan betrayed her.
The Curse: This is where it becomes even more important. The curse is born of the utter seething hatred that Maleficent has for humans, for lust for power, and most of all over the lie that is "true love" - which she uses as the one, single exception to her curse as the perfect "fuck you" to Stefan. It's a long and slow lesson that shows her that she CAN really love someone, even if she doesn't recognize it herself initially, because she is still thinking in terms of romantic love being the only true love - which it isn't. This is exacerbated even more because she's the one who brings the prince into the castle in an attempt to save Aurora (which was handled fantastically when he feels awkward about kissing her even though he would like to, and the three fairies still think that they're managing all on their own). All of the little actions that Maleficent made over the years, and the ways that Aurora brought back the light into her life is why it's important that Maleficent's love breaks the curse - especially after her own magic failed to be strong enough. What's exceptionally meaningful is that after that, Aurora brings back LITERALLY everything Maleficent lost when she frees Maleficent's wings - finally finishing in undoing everything that Stefan did to cause pain and darkness to fall over the Moors. In this story, Maleficent doesn't need to transform into the dragon to overcome and finally defeat Stefan, because she already WAS as powerful as she ever needed to be from the start (plus, it let Diaval actually transform into something amazing).
Then you round out with the happily ever after, and Aurora became queen of the Moors because there was a real peace and understanding built out of a mutual love, and not out of something dependent on pure romance - and THAT is probably every single reason that I absolutely loved Maleficent.