i was under the impression that desease spreads rather quickly, and there where europeans treaking around the interier before it was held (wasn't there two spainards that got completly lost in north america) by europeans and even before europeans even really knew there was stuff there.
i also read somewhere that the first europeans on the west coast found villages destroyed fairly recently by desease.
second desease is not confined to one person traveling the entire distance. say tribe a is on the east coast and tribe z is on the west. tribe a meets a european. infected contagious dude from tribe a doesn't really feel sick yet meets with a guy from tribe b, infecting him. tribe b is now infected and dude from them meets with tribe c, and on and on and on till you get to tribe z.
and think about the black plauge. that came pretty damn close to destroying europe. contagious desease can really throw things back. i had one history prof hypothisis that, if not for the black plauge, europeans would have made it to the americans quite a bit earilier.