The game has to transfer a lot of data, unfortunately. 100kbps up may be pushing it, if you're the host in a sufficiently large game. The main culprit for lag is generally packet loss, because with TCP it then has to resend and try again, etc. I may need to look into a UDP solution like I once had in the game, just for the apparently-higher-packet-loss-rate networks that a lot of people are on. I have 7000 down and 368 up, as do most of my alpha testers, and we can play perfectly lag-free with two in the Raleigh area, two in the Boston area, in the US.
This is something I'll have to investigate more next week, but any other information on your networks would be much appreciated. There are a few ways to get some network statistics on dropped packets, etc, but off the top of my head I don't know of any good ones. Otherwise, it might just be that your upload speed is more constrained during hours you are playing than it is supposed to be -- doing a speed test at that time would probably be helpful.
This game has some of the higher network requirements around, I think, which makes it a bit more challenging. I'll also look into some high-latency modes that you might be able to try in order to give more time to the network. That might be a solution right there, I'm not sure.