nRelate was never a good solution. They tried to make it SEO-friendly, but it just never worked correctly.

If you're looking for an alternative, http://relatedpostsforwp.com/ is what I've been using and recommending since it was released. There's both free and paid versions available and it's a much better option than any of the others I've tested.