Indeed. Just the other day I split my sitemap into four pages in response to GoogleGuy's suggestion. If advice like that comes from the horse's mouth, It think we ignore it at our peril.
Perhaps Google just stops spidering after 100 links, or maybe your site's relevance is subtly downgraded. Perhaps this is why my site ranks several places below where I think it ought to, according to PR and number of links? Maybe I'll find out at the next re-indexing?