As is often the way, writing the previous post put me in the mood to have another shot at fixing the problem.
One of the things missing from the previous post was me mentioning I'd temporarily switched the Xbox 360 over to a fixed IP address. The Xbox live network recommendations require a couple of ports to be forwarded, which means the router needs to know where they go to!
I'd put the MAC Address for the 360 into my DHCP server but simply hadn't got around to switching the config on the Xbox over from manual to automatic. I didn't think it would make a difference given that either way is assigning it the exact same IP..
So I switched it over, and of course it works. I'm curious as to what it is about the 'manual' IP mode which requires a connection test before it'll connect, however I think I'm just going to go with 'if it ain't broke, don't worry about it' on this one.