@JuiceRocket
When you switch between wireless and wired, are you power cycling your Xbox, modem and router? If not, switch back to a wire and go through those power cycling steps again. If that still doesn't help, try using alternate DNS settings with these steps: from the Xbox home screen, go to Settings > Network > Advanced settings > DNS settings > Manual. (If Settings doesn't appear on the home screen, select My Games & Apps, then Settings). From there, enter the Primary DNS as "208.67.222.222" and the Secondary DNS as "208.67.220.220". If that doesn't help, try using the google DNS servers which are: primary alt number 8.8.8.8 - secondary alt number 8.8.4.4.
@Godfather_Smoove
Try those same instructions for alternate DNS settings. Also, are you on a wired or wireless connection?