Did you run the config program at all before patching or after nuking the user data? For some people, this has resolved that issue.

If that fails (or you already did it), connect the PC directly to the modem, OR if you are using wireless, try a wired connection (the game is slightly better about lost packets these days, however, that does nothing for you before you actually patch it).