Tonight I went to the datacenter and changed our incoming internet pipe to full duplex mode. This will give us a few more usable megabits of bandwidth, making it much less likely that we'll max out our bandwidth. It also cuts off a few milleseconds of latency.
As always, I need to thank the wonderful support staff at InterNAP for making everything so easy! I called, and within 10 minutes we had the link forced to full duplex with no interruption of service.
Why were we in half duplex mode in the first place? Good question. Their side was set to autonegotiate as was ours. Maybe it's the media converter? Maybe its our switch? Setting our switch to full duplex (and leaving theirs on auto) only made things worse. But now both sides of the link are happy, I'm happy, and our users should be happy too!