We certainly seem to have ruled out the router but I'm hard pressed to think of anything wrong with the settings on the xbox. This might be a silly question but have you tried resetting the router (power off for a minute, then power back on); and then trying to have the xbox set up the network automatically?
That did actually once solve it for me. My router was hanging on to some old settings and my xbox was insisting on connecting to a specific IP that my router thought was assigned to another device. Resetting the router wiped its memory of IP addresses, and then when the xbox requested the one it thought it should have, it got its wish
So basically they were both being douchebags with one another, but were made to kiss and make up.