<p>I'm building a auto updater and I need to know what kind of upload speeds people get on a 56K modem?</p>

Theoretically 33.6 kbit/s upload = 4.2 kB/s[1].
From own experience, I would say half of that :)
[1]
http://en.wikipedia.org/wiki/ITU-T_V-Series_Recommendations#Simultaneous_transmission_of_data_and_other_signals