I used to experience the same thing with FP 2000. For some inexplicable reason it would suddenly slow right down in the middle of an upload.
It doesn't happen now, with FP 2003 and a broadband connection, and I can't provide any answers - has it always been like this? If it has, you might have a word with your web host.
Are you updating an existing site, or publishing for the first time?
Have you tried an upload via an FTP program? If you have one try creating a special directory and upload anything that's not your site (a few word docs for instance) and see how that runs by comparison.