Personally i'd start from scratch. Hard reset your router (this will require you to reconfigure for WAN side as well mind) and then reset your 360 to default network settings.
From here, ensure uPnP is enabled and then connect your 360.
Also, you mentioned that you only appear to be having the issue over WiFi? What encryption type are you using? My 360 doesn't appear to be having any problems using WPA, but for troubleshooting purposes it might be worth giving WEP a go. (I dont believe this will have any effect, but it's worth a shot)