How about Sabriel by Garth Nix? It was recently released as a 25th anniversary edition and it seems to fit your description: dark fantasy, YA and a little romance thrown in.
Official page
You can probably get a sample for kindle if you have an amazon account to see if you like the style of Garth Nix' writing.