Two things to try:

1. You're connecting via wireless? Do you have 3g capability and, if so, have you tried connecting that way to see if it makes any difference?
2. Have you synched fairly recently to make sure your firmware is up to date?