Is the network behind you relatively slow?
I used to have that problem when I had DSL. It went away after I switched to a much faster cable connection. My WiFi network was faster than the DSL network behind it, and iCloud backups would bring my network to its knees with congestion, etc.
New phones, ios updates, etc all make the backups larger until you've done the first one.
-David