So, I had to stop using my Wired Connection because my Wife wanted to have her PC upstairs tethered. So, I go into my Xbox 360 S, enter the info, enter the MAC address in my Router. Everything looks good, until it tries to test the connection. The password is incorrect. Both router and Xbox says this, yet I enter the same password on multiple devices without any problem. I also need to mention my router logs have it denying my Xbox, saying incorrect Security. So why is this happening, is it Xbox related?
I found out that while most places including here and everywhere on Xbox site where it tells you how to either connect wireless or finding your password on your router. Either way Xbox360 does support connecting to a wireless router using WPA2(AES). However, it is not an accepted algorithm. It will accept WEP or WPA with TPK. This is really a hit and miss issue.
Thanks to @Frank for troubleshooting the issue.