It's not a connection strength issue. I'm right next to the router and the network strength is the maximum possible.

I'm already using TKIP.

I installed wireless-tools and ran iwevent. I'm copying what I saw by hand so I'll summarize:

wlan0 Custom driver event:ASSOCINFO (ReqIEs=<stuff> Resp=<stuff>)
wlan0 New Access Point/Cell address:<router MAC>
wlan0 New Access Point/Cell address:Not-Associated
wlan0 Set Frequency:2.412 Ghz (Channel 1)
wlan0 Scan request completed

Then repeat that block ad infinitum. Not terribly helpful, I know...