Sound's like your web server is not very powerful. I would switch over to using background processing (in your admin panel) for your videos. This way, once the video is uploaded, it converts in the background.

Also, the actual speed of the upload is related to your internet connection. What is your Internet connection's upload speed?