Many people have noticed that the Xbox and Xbox 360 will not obtain an IP address from a Mac running Internet Sharing using DHCP. (Apparently some other devices have the same problem, but I don't have any of them to test with.) One workaround is to simply set the Xbox to use a static IP, DNS server(s), etc. That will certainly work, but it may be inconvenient and is definitely inelegant.
This hint will allow your Xbox to obtain its IP, DNS info, and so on from the Mac using DHCP. You need to have administrator privileges on the Mac in question, and the procedure is different on 10.4 vs. 10.5. (Presumably older systems were similar to 10.4, but I haven't tested on anything older than 10.4.10.).
10.4:
I haven't had much time to interact with the 10.4 machine I have access to, so I haven't tested this as much. Some variation on this procedure may be necessary to get the change to stick -- in particular, you may need to perform it more than once, or start and/or stop Internet Sharing before performing it. Also, the restart at the end may be unnecessary (though you do need to start and stop Internet Sharing somehow). Please post your experience in the comments, if someone hasn't already.
<key>reply_threshold_seconds</key>
<integer>4</integer>Mac OS X Hints
http://hints.macworld.com/article.php?story=20071223001432304