My search for the best news reading application for Linux is over. After trying out several applications like Straw, Akregator etc., I finally settled on Liferea. Liferea is a GTK based application which is ideal for the gnome desktop. Though it does not have features like discovering multiple feeds within a website, emailing posts etc., it serves its purpose as a basic yet powerful news reader. The obligatory screen shot is below (click to enlarge).
To install just do:
sudo apt-get install liferea
Most of the time, just giving the URL of the website is enough to add a feed!