Even though the links are "nofollow", Google has always followed those links to checkout the pages they link to. However, Google says that those links don't count when considering link juice or PageRank. This may be true, but it also may be true that having only "dofollow" links isn't natural, so having a mix of dofollow and nofollow is probably the best. And don't forget, a nofollow link on a high traffic site can still bring direct traffic.
Here is how google handle nofollowed links: http://www.google.com/support/webmasters/bin/answer.py?answer=96569