Oh it drove me crazy and still nothing worked (thanks for all the suggestions!)

Checked everything you suggested and in the end I just bought a new router. Problem solved!

Why though would it work for 20 minutes at a time? Why, when I did all the checks from the xbox menu did it pass all the tests with everything open and ready to go. Weird. Oh well... :S