Sam Ruby is in the process of upgrading to Gutsy, and just pointed out an open source news reader that I hadn't checked out before called Liferea. I've seen it mentioned before, but had forgotten about it. I just snagged it with a quick "aptitude install liferea", exported my feeds from OMGWTFBBQ (my web based newsreader I use daily) and imported the OPML. Liferea isn't bad, actually... I like the river of news view, and it seems to format everything very well. I prefer online readers better, but it's nice to have alternatives.
BTW, aptitude is better than apt-get on Ubuntu - it seems to keep the deb database in sync better. It takes a while for your fingers to get used to typing that extra "i" before hitting tab, but once you do it works the same