After upgrading Mac OS X to 10.0.4 via Ethernet, it still did not work. The problem was solved by removing /var/db/SystemConfiguration/*, rebooting, and reconfiguring my network. I did not bother trying to see what specifically caused this, I just started from scratch.
Hopefully this can help somebody else.
[Editor's note: I'm not sure how many people are still running an older version of OS X, but if you are, the above hint may be of assistance.]

