Ok based on your responses so far this has nothing to do with your router (so forget that for now) and all to do with your PC that you share the connection to.
I would unshare any connections on your PC and restart it and go into your Xbox and choose to reset your network settings to factory defaults
We are then "starting afresh"
Please look at one or both of these guides for help on this set-up:-
support.xbox.com/.../win-computer (Microsoft Official Guide)
www.unofficialguidetolive.co.uk/.../ics-bridging-guide (Unofficial Guide if you are still struggling)
Setting up ICS is easy to get wrong, if you choose to share the wrong adapter or have a third party firewall on your PC like Zonealarm/Mcafee/ESET etc etc they can also affect your connection (e.g. ip address failed)
Let us know how it goes, try the first link first if that doesn't sort you out use the second as I have other troubleshooting info / help on their , videos etc
Also you say you have tried bridging in the past , what happened with that what message did that fail with?