For what it's worth, Facebook is also doing the same thing with a darker left border:

For me, that is way too subtle, and even when I did notice it, I had no idea what it was — I only figured it out when I inspected the element and saw the CSS class was unseenItem.
I'm not sure changing the background color is ideal either as it has the connotation of a more permanent indicator.
You want something that does not change position, or appearance too drastically (so that a refresh doesn't look completely different). I think a badge or something similar is the best approach for this. The Facebook solution is a badge of sorts, but it's too subtle and the still-dull color doesn't say "new".
If I were Facebook, I would have gone with something much more obvious, perhaps big enough to be a hover target for a help tooltip, such as dark color in a corner on the left or right side (both included for comparison):

It's not quite the same concept, but I have used a corner wrap on an image to indicate new items on a customer's store (in this case, new is exciting, not just informational):
