I'm not sure if the XBox live team have an official bug reporting mechanism, so I'll put this post here in the interim and hopefully a search engine or two will pick up on it.

This has no bearing on the NXE that launched today, I've just coincidentally solved the problem.

Symptoms

XBox 360 fails to automatically connect to xbox live after power on.  If you then go and perform a network test, it'll succeed.  Following this, live will connect fine until you power off the xbox for a time greater than a minute or two.

Cause

There appears to be a bug in the code that deals with manual network configuration of the xbox 360.  If you manually assign the console an IP address and then manually assign a DNS server but leave the DNS server discovery setting to automatic, the xbox fails to do a DNS lookup, either automatically or manually, on system startup.

Solution

If you manually assign an IP address and DNS server, ensure that the DNS lookup mode is also set to manual.

I have no idea why the console lets you configure a DNS server and then gives you the choice to use it or not, I'd have thought it'd be one or the other, and it's a very easy mistake to make and quite tricky to diagnose.