Ok.
After hours and hours of research it would appear as if Apple's MacBook drivers suck ass.
I was able to get the computer connected to the router somehow. I'm not really sure at this point what I did to be able to connect.
I've also tracked down the cause of the wireless slowdown. According the
this thread at Apple's discussion boards, connecting a MacBook to a D-Link router will result in a 37% loss of packets which just happens to be exactly how much slower my MacBook is wirelessly.
I guess the D-Link is going back today too.
Any suggestions on a router that should be good?