Alright, I've ensured that the reserved address is correct (no change btw so I was fine there).
I've furthermore modified my network to have no security (temporarily).
When I power cycle the xbox and attempt to connect to the network, I first managed to get to the third stage (internet - > xbl) but it failed saying live was not responding.
When I tried a second time it failed in the first stage.
When I look at the ip settings that were "automatically" assigned, they don't seem to relate to my network at all. IP: 169.254.186.52, subnet 255.255.0.0 and no gateway.
This is pretty much similar behavior that I was seeing with WPA 2 enabled as well in either mixed or N mode.
Randomly throughout my ordeal over the last few days I have managed to connect to XBL but not enough to sustain a power cycle.
What next?