There are several issues that may make uploading large files difficult from slow connections.

All servers have upper limits of size and speed for uploading. Some of these can be over-ridden, but this depends on the amount of control you have over the server machine. 

Current settings on this site are

post_max_size

8M

upload_max_filesize

2M

memory_limit

126M

max_execution_time

30

Each of these must be comfortably above the size of the file you are trying to upload. The memory_limit should be several times the filesize if you are attempting video conversion on the server.
The upload time taken must be within the range of max_execution_time.

Attempting to increase these values (which can sometimes be done by the server administrator) should not be done without being aware of the side effects.
Increasing the max_execution_time too far for example, runs the risk of freezing your entire site in times of high traffic as failed requests will take a long time to drop, eventually tying up the server.

To change these values, you must edit the server settings, either through the site hosting control panel (not Drupal) or directly as sysadmin on the machine.

FTP

The alternative, and much more reliable method, is to upload files via FTP. This is a totally different method from Drupal CMS file management, and so is not fully integrated withthe web interface. You need an FTP program (both Firefox and IE can do this for you if you enter the location ftp://sitename.co.nz/) and login with the appropriate username and password (which may not be the same as your Drupal password!)

Use FTP to place your large files in the appropriate place in the Drupal /files/ directory. The hard part is you now have to link to that file by entering its full path manually. You probably cannot locate that file using the Drupal file attachment interfaces alone.

If you have FTP-d your file up to /files/videos/my_giant_video.flv you need to enter that path (With leading slash) when linking or referring to it when editing your content. (if your site is not in website root, extra complications apply)