I found that I had to go into Network Settings and disable the local area network connection, then re-enable it in order for it to pickup a DHCP lease after I switched from NAT to Bridged networking.

It is possible to bridge a guest to two separate physical interfaces on the host, but I do not think you will be able to accomplish what you want. The problem is that ICS in Windows doesn't bridge network connections. It does its own NAT. There are two ways this could typically go.

First, you have a router upstream of your Mac. This router likely does its own NAT. That would mean that the Xbox is now behind two layers of NAT, and unless UPnP is far more frightening than I think, the double-NAT would prevent the Xbox from mapping ports on the upstream router.

Second, your Mac has a public IP address on it and you just have a bridge to your ISP's network. In this case, most ISPs don't give normal users multiple public addresses, so Windows would have to share the Mac's address. Again, we have the double-NAT thing going on.

How is your Mac connected to the Internet?

So you're connecting to your router wirelessly, and plug the Xbox into the ethernet port? How many network interfaces show up in Windows when you're running it as a guest? How many virtual NICs do you have configured for the VM? You'll need two virtual NICs, you should be able to make them both bridged. First try without the Xbox plugged in so you can figure out which one gives Internet access (i.e. which one is bridged to the Airport), then plug the Xbox in and do your Windows ICS. I don't see a reason why that wouldn't work