The July 2004 Google update has brought up a new myth that needs to be squashed right now. First let me start with a brief background on why this came out.
Google updated the backlinks a few days ago, those backlinks seem to be missing a page's most "valued" links (i.e. Yahoo Directory, DMOZ and others). Many page's backlinks jumped to two or three times the number, some remained constant and some were lower. People are upset, afraid, nervous and confused. The only valid emotional response for this update would be confused. There is no reason to be upset, afraid or nervous because most rankings have remained constant.
Its critical to point out that the rankings have, for the most part, remained where they are for most keyword phrases. Because the link query in Google is showing weird (spammy) backlinks, this does not mean that your link popularity is better or worse off. It, for sure, DOES NOT mean that Google is less relevant.
Google's results for ordinary keyword searches have been unaffected (as far as I have seen). The only real difference are the results returned for the link query, which does not (and should not) define relevancy.